Graph Treewidth and Geometric Thickness Parameters

Dujmović, Vida and Wood, David R. (2006) Graph Treewidth and Geometric Thickness Parameters. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005 , pp. 129-140(Official URL: http://dx.doi.org/10.1007/11618058_13).

Full text not available from this repository.

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 t(G). By restricting the edges to be straight, we obtain the geometric thickness gt(G). By further restricting the vertices to be in convex position, we obtain the book thickness _t(G). This paper studies the relationship between these parameters and the treewidth of G. Let T_k denote the class of graphs with treewidth at most k. Let t{T_k} / gt{T_k} / _t{T_k} denote the maximum thickness / geometric thickness / book thickness of a graph in T_k. We prove that : t{T_k}=gt{T_k}=ceil{k/2}, and _t{T_k}=k for k<=2, and _t{T_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 _t{T_k}=k for all k. Analogous results are proved for outerthickness, arboricity, and star-arboricity.

Item Type: Conference Paper
Additional Information: 10.1007/11618058_13
Classifications: Z Theory > Z.001 General
Z Theory > Z.250 Geometry
URI: http://gdea.informatik.uni-koeln.de/id/eprint/687

Actions (login required)

View Item View Item