Graph Treewidth and Geometric Thickness ParametersDujmović, Vida and Wood, David R. (2006) Graph Treewidth and Geometric Thickness Parameters. In: Graph Drawing 13th International Symposium, GD 2005, September 1214, 2005 , pp. 129140(Official URL: http://dx.doi.org/10.1007/11618058_13). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/11618058_13
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 stararboricity.
Actions (login required)
