Tree-partitions of k-trees with applications in graph layout

Vida Dujmovic; David R. Wood

doi:10.1007/978-3-540-39890-5_18

Tree-partitions of k-trees with applications in graph layout

Vida Dujmovic, David R. Wood

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

8 Citations (Scopus)

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.

Original language	English
Title of host publication	Graph-theoretic concepts in computer science
Publisher	Springer
Pages	205-217
Number of pages	13
Volume	2880
DOIs	https://doi.org/10.1007/978-3-540-39890-5_18
Publication status	Published - 2003
Externally published	Yes

Publication series

Name	Lecture Notes in Comput. Sci.
Publisher	Springer, Berlin

Access to Document

10.1007/978-3-540-39890-5_18

Cite this

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

}

TY - GEN

T1 - Tree-partitions of k-trees with applications in graph layout

AU - Dujmovic, Vida

AU - Wood, David R.

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-540-39890-5_18

DO - 10.1007/978-3-540-39890-5_18

M3 - Conference Paper

VL - 2880

T3 - Lecture Notes in Comput. Sci.

SP - 205

EP - 217

BT - Graph-theoretic concepts in computer science

PB - Springer

ER -