SucheA lower bound for the treewidth of k-outerplanar graphs
Frank Kammer, Torsten Tholey
2009-07
in: Universität Augsburg
Technical Report, Institute of Computer Science, University of Augsburg, April 2009
tree-decomposition of small width is given. Unfortunately, all known algorithms
computing, for general graphs, a tree decomposition of width
k, if one exists, have a running time exponential in k. However, Bodlaender
observed that each k-outerplanar graph has a tree decomposition
of width at most 3k − 1 and his analysis implicitly leads to an O(kn)-
time algorithm for computing such a tree-decomposition. In this paper
we show that the bound 3k − 1 is tight, i.e., for every k 2 IN, there are
k-outerplanar graphs having treewidth 3k − 1.
Downloads:
- A lower bound for the treewidth of k-outerplanar graphs - (tp2009-07.pdf, 654 KB)