2005/10/07 by Vida Dujmović, David R. Wood
Computer Science · Mathematics · #Algorithms and Data Compression #Bounded function #Combinatorics #Computational Geometry and Mesh Generation #Degeneracy (biology) #Digital Image Processing Techniques #Directed acyclic graph #Discrete mathematics #Geometry #Graph #Graph drawing #Grid #Mathematics #Planar graph #Upper and lower bounds #Vertex (graph theory) #math.CO
paper · pdf · doi:10.1007/s11083-006-9028-y
published as Order 23:1-20, 2006
arxiv created 2005/10/07 · openalex publication_date 2006/02/01 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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(n3/2) 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 (n3) volume, which is tight for the complete dag. The previous best upper bound was O(n4). Our main result is that every c-colourable directed acyclic graph (c constant) has an upward three-dimensional grid drawing with O(n2) volume. This result matches the bound in the undirected case, and improves the best known bound from O(n3) for many classes of directed acyclic graphs, including planar, series parallel, and outerplanar.