## Graph Treewidth and Geometric Thickness Parameters
Dujmović, Vida and Wood, David R.
(2006)
Full text not available from this repository. ## AbstractConsider 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.
Repository Staff Only: item control page References |