### Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 553-579 |

Number of pages | 27 |

Journal | SIAM Journal on Computing |

Volume | 34 |

Issue number | 3 |

DOIs | |

Publication status | Published - 2005 |

Externally published | Yes |

## Cite this

Dujmovic, V., Morin, P., & Wood, D. R. (2005). Layout of graphs with bounded tree-width.

*SIAM Journal on Computing*,*34*(3), 553-579. https://doi.org/10.1137/S0097539702416141