Mathematics – Combinatorics
Scientific paper
2005-10-03
Order 23:1-20, 2006
Mathematics
Combinatorics
Scientific paper
10.1007/s11083-006-9028-y
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.
Dujmovic Vida
Wood David R.
No associations
LandOfFree
Upward Three-Dimensional Grid Drawings of Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Upward Three-Dimensional Grid Drawings of Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Upward Three-Dimensional Grid Drawings of Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-134556