@inproceedings{30017e51694445da84d3790dfcf677ee,
title = "Tree-partitions of k-trees with applications in graph layout",
abstract = "A tree-partition of a graph is a partition of its vertices into 'bags' such that contracting each bag into a single vertex gives a forest. It is proved that every k-tree has a tree-partition such that each bag induces a (k - 1)-tree, amongst other properties. Applications of this result to two well-studied models of graph layout are presented. First it is proved that graphs of bounded tree-width have bounded queue-number, thus resolving an open problem due to Ganley and Heath [2001] and disproving a conjecture of Pemmaraju [1992], This result provides renewed hope for the positive resolution of a number of open problems regarding queue layouts. In a related result, it is proved that graphs of bounded tree-width have three-dimensional straight-line grid drawings with linear volume, which represents the largest known class of graphs with such drawings. ",
author = "Vida Dujmovic and Wood, {David R.}",
year = "2003",
doi = "10.1007/978-3-540-39890-5_18",
language = "English",
volume = "2880",
series = "Lecture Notes in Comput. Sci.",
publisher = "Springer",
pages = "205--217",
booktitle = "Graph-theoretic concepts in computer science",
address = "Switzerland",
}