Upward Three-Dimensional Grid Drawings of Graphs

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. Our first main result is that every -vertex graph with bounded degeneracy has a three-dimensional grid drawing with volume. This is the largest known class of graphs that have such drawings. A three-dimensional grid drawing of a directed acyclic graph (dag) is upward if every arc points up in the -direction. We prove that every dag has an upward three-dimensional grid drawing with volume, which is tight for the complete dag. The previous best upper bound was . Our main result concerning upward drawings is that every -colourable dag ( constant) has an upward three-dimensional grid drawing with volume. This result matches the bound in the undirected case, and improves the best known bound from for many classes of dags, including planar, series parallel, and outerplanar. Improved bounds are also obtained for tree dags. We prove a strong relationship between upward three-dimensional grid drawings, upward track layouts, and upward queue layouts. Finally, we study upward three-dimensional grid drawings with bends in the edges.Research of Vida Dujmovi is supported by NSERC. Research of David Wood is supported by the Government of Spain grant MEC SB2003-0270 and by the projects MCYT-FEDER BFM2003-00368 and Gen. Cat 2001SGR00224.