Layout of graphs with bounded tree-width

A queue layout of a graph consists of a total order of the vertices, and a partition of the edges into queues, such that no two edges in the same queue are nested. The minimum number of queues in a queue layout of a graph is its queue-number. A three-dimensional (straight-line grid) drawing of a graph represents the vertices by points in Z3 and the edges by noncrossing line-segments. This paper contributes three main results: (1) It is proved that the minimum volume of a certain type of three-dimensional drawing of a graph G is closely related to the queue-number of G. In particular, if G is an n-vertex member of a proper minor-closed family of graphs (such as a planar graph), then G has a Ο(1) × Ο(1) × Ο(n) drawing if and only if G has a Ο(1) queue-number. (2) It is proved that the queue-number is bounded by the tree-width, thus resolving an open problem due to Ganley and Heath [Discrete Appl. Math., 109 (2001), pp. 215-221] and disproving a conjecture of Pemmaraju [Exploring the Powers of Stacks and Queues via Graph Layouts, Ph. D. thesis, Virginia Polytechnic Institute and State University, Blacksburg, VA, 1992], This result provides renewed hope for the positive resolution of a number of open problems in the theory of queue layouts. (3) It is proved that graphs of bounded tree-width have three-dimensional drawings with Ο(n) volume. This is the most general family of graphs known to admit three-dimensional drawings with Ο(n) volume. The proofs depend upon our results regarding track layouts and tree-partitions of graphs, which may be of independent interest. © 2005 Society for Industrial and Applied Mathematics queue layout, queue-number, three-dimensional graph drawing, tree-partition, treepartition-width, tree-width, k-tree, track layout, track-number, acyclic coloring, acyclic chromatic number.