Queue Layouts and Three-Dimensional Straight-Line Grid Drawings

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(n2) 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 con-sists of a linear order 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 . Let G be a mem-ber 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) F (n) 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 log2 n) to O(n)