Upward Three-Dimensional Grid Drawings of Graphs
| dc.creator | Dujmović, Vida | |
| dc.creator | Wood, David R. | |
| dc.date | 2005-10-03 | |
| dc.date | 2005-10-07 | |
| dc.date.accessioned | 2026-07-07T06:47:08Z | |
| dc.date.available | 2026-07-07T06:47:08Z | |
| dc.description | A \emph{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^{3/2})$ volume. This is the broadest class of graphs admiting such drawings. A three-dimensional grid drawing of a directed graph is \emph{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^3)$ volume, which is tight for the complete dag. The previous best upper bound was $O(n^4)$. Our main result is that every $c$-colourable directed acyclic graph ($c$ constant) has an upward three-dimensional grid drawing with $O(n^2)$ volume. This result matches the bound in the undirected case, and improves the best known bound from $O(n^3)$ for many classes of directed acyclic graphs, including planar, series parallel, and outerplanar. | |
| dc.identifier | https://arxiv.org/abs/math/0510051 | |
| dc.identifier | http://arxiv.org/abs/math/0510051 | |
| dc.identifier | Order 23:1-20, 2006 | |
| dc.identifier | doi:10.1007/s11083-006-9028-y | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/103561 | |
| dc.subject | Combinatorics | |
| dc.title | Upward Three-Dimensional Grid Drawings of Graphs | |
| dc.type | text |