20050630
Layout of graphs with bounded treewidth
Publication
Publication
SIAM Journal on Computing , Volume 34  Issue 3 p. 553 579
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 queuenumber. A threedimensional (straightline grid) drawing of a graph represents the vertices by points in Z3 and the edges by noncrossing linesegments. This paper contributes three main results: (1) It is proved that the minimum volume of a certain type of threedimensional drawing of a graph G is closely related to the queuenumber of G. In particular, if G is an nvertex member of a proper minorclosed family of graphs (such as a planar graph), then G has a Ο(1) × Ο(1) × Ο(n) drawing if and only if G has a Ο(1) queuenumber. (2) It is proved that the queuenumber is bounded by the treewidth, thus resolving an open problem due to Ganley and Heath [Discrete Appl. Math., 109 (2001), pp. 215221] 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 treewidth have threedimensional drawings with Ο(n) volume. This is the most general family of graphs known to admit threedimensional drawings with Ο(n) volume. The proofs depend upon our results regarding track layouts and treepartitions of graphs, which may be of independent interest.
Additional Metadata  

dx.doi.org/10.1137/S0097539702416141  
SIAM Journal on Computing  
Organisation  School of Computer Science 
Dujmović, V, Morin, P, & Wood, D. (2005). Layout of graphs with bounded treewidth. SIAM Journal on Computing, 34(3), 553–579. doi:10.1137/S0097539702416141
