Graph Treewidth and Geometric Thickness Parameters |
| |
Authors: | Vida Dujmovic David R Wood |
| |
Institution: | (1) Department of Mathematics and Statistics, McGill University, Montreal, Quebec, Canada H3A 2A7;(2) Departament de Matematica Aplicada II, Universitat Politecnica de Catalunya, 08034 Barcelona, Spain |
| |
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. By restricting the edges to be straight, we obtain
the geometric thickness. By additionally 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 ⌈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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|