A lower bound for the treewidth of k-outerplanar graphs

Many optimization problems can be solved efficiently if a 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