Upward Three-Dimensional Grid Drawings of Graphs

Original · EN

A three-dimensional grid drawing of a graph is a placement of the vertices at distinct points with integer coordinates, such that the straight line segments representing the edges do not cross. Our aim is to produce three-dimensional grid drawings with small bounding box volume. We prove that every n-vertex graph with bounded degeneracy has a three-dimensional grid drawing with O(n³/²) volume. This is the broadest class of graphs admiting such drawings. A three-dimensional grid drawing of a directed graph is upward if every arc points up in the z-direction. We prove that every directed acyclic graph has an upward three-dimensional grid drawing with (n³) volume, which is tight for the complete dag. The previous best upper bound was O(n⁴). Our main result is that every c-colourable directed acyclic graph (c constant) has an upward three-dimensional grid drawing with O(n²) volume. This result matches the bound in the undirected case, and improves the best known bound from O(n³) for many classes of directed acyclic graphs, including planar, series parallel, and outerplanar.