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

Vida Dujmovic, David R. Wood

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-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 languageEnglish
Title of host publicationGraph-theoretic concepts in computer science
PublisherSpringer
Pages205-217
Number of pages13
Volume2880
DOIs
Publication statusPublished - 2003
Externally publishedYes

Publication series

NameLecture Notes in Comput. Sci.
PublisherSpringer, Berlin

Cite this