Mathematics – Combinatorics
Scientific paper
2005-03-24
Discrete & Computational Geometry 37(4):641-670, 2007
Mathematics
Combinatorics
A preliminary version of this paper appeared in the "Proceedings of the 13th International Symposium on Graph Drawing" (GD '05
Scientific paper
10.1007/s00454-007-1318-7
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". By restricting the edges to be straight, we obtain the "geometric thickness". By further restricting the vertices to be in convex position, we obtain the "book thickness". This paper studies the relationship between these parameters and treewidth. Our first main result states that for graphs of treewidth k, the maximum thickness and the maximum geometric thickness both equal ceil{k/2}. This says that the lower bound for thickness can be matched by an upper bound, even in the more restrictive geometric setting. Our second main result states that for graphs of treewidth k, the maximum book thickness equals k if k <= 2 and equals k+1 if k >= 3. This refutes a conjecture of Ganley and Heath [Discrete Appl. Math. 109(3):215-221, 2001]. Analogous results are proved for outerthickness, arboricity, and star-arboricity.
Dujmovic Vida
Wood David R.
No associations
LandOfFree
Graph Treewidth and Geometric Thickness Parameters does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Graph Treewidth and Geometric Thickness Parameters, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph Treewidth and Geometric Thickness Parameters will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-587026