Graph treewidth and geometric thickness parameters

Vida Dujmovic, David R. Wood

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

5 Citations (Scopus)

Abstract

Consider a drawing of a graph G in the plane such that crossing edges are coloured differently. The minimum number of colours, taken over all drawings of G, is the classical graph parameter thickness θ(G). By restricting the edges to be straight, we obtain the geometric thickness θ̄(G). By further restricting the vertices to be in convex position, we obtain the book thickness bt(G). This paper studies the relationship between these parameters and the treewidth of G. Let θ(Τk) / θ̄(Τ k) / bt(Τk) denote the maximum thickness / geometric thickness / book thickness of a graph with treewidth at most k. We prove that: - θ(Τk) = θ̄(Τk) = [k/2], and - bt(Τk) = k for k ≤ 2, and bt(Τk) = k + 1 for k ≥ 3. The first result says that the lower bound for thickness can be matched by an upper bound, even in the more restrictive geometric setting. The second result disproves the conjecture of Ganley and Heath [Discrete Appl, Math. 2001] that bt(Τk) = k for all k. Analogous results are proved for outerthickness, arboricity, and star-arboricity.
Original languageEnglish
Title of host publicationGraph drawing
PublisherSpringer
Pages129-140
Number of pages12
Volume3843
DOIs
Publication statusPublished - 2006
Externally publishedYes

Publication series

NameLecture Notes in Comput. Sci.
PublisherSpringer, Berlin

Cite this

Dujmovic, V., & Wood, D. R. (2006). Graph treewidth and geometric thickness parameters. In Graph drawing (Vol. 3843, pp. 129-140). (Lecture Notes in Comput. Sci.). Springer. https://doi.org/10.1007/11618058_13