Carleton University
Technical Report TR-02-02
June 2002
Queue Layouts and Three-Dimensional Straight-Line Grid Drawings
Abstract
A famous result due to de Fraysseix, Pach, and Pollack [Combinatorica, 1990] and Schnyder [Order, 1989] states that every n-vertex planar graph has a (two-dimensional) straight-line grid drawing with O(n^2) area. A three-dimensional straight-line grid drawing of a graph represents the vertices by grid-points in 3-space and the edges by non-crossing line segments. This research is motivated by the following question of Felsner, Liotta, and Wismath [Graph Drawing ’01, Lecture Notes in Comput. Sci., 2002]: does every planar graph have a three-dimensional straight-line grid drawing with O(n) volume? A queue layout consists of a linear order sigma of the vertices of a graph, and a partition of the edges into queues, such that no two edges in the same queue are nested with respect to sigma. Let G be a member of a proper minor-closed family of graphs (such as a planar graph), and let F(n) be a set of functions closed under taking polynomials (such as O(1) or polylog n). We prove that G has a F(n)\times F(n)\times O(n) straight-line grid drawing if and only if G has a queue layout with F(n) queues. Thus the above question is closely related to the open problem of Heath, Leighton, and Rosenberg [SIAM J. Discrete Math., 1992], who ask whether every planar graph has O(1) queuenumber? As a corollary we improve the best known upper bound on the volume of three-dimensional straight-line grid drawings of series-parallel graphs from O(n\log^2n) to O(n).