@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",

}