Optimal tree-decompositions with bags of bounded treewidth

Source abstract

Abstract We prove that several natural graph classes have tree-decompositions with minimum width such that each bag has bounded treewidth. For example, every planar graph has a tree-decomposition with minimum width such that each bag has treewidth at most 3. This treewidth bound is best possible. More generally, every graph of Euler genus g g $g$ has a tree-decomposition with minimum width such that each bag has treewidth in upper O left parenthesis g right parenthesis O ( g ) $O(g)$ . This treewidth bound is best possible. Most generally, every upper K Subscript p K p $K_p$ -minor-free graph has a tree-decomposition with minimum width such that each bag has treewidth at most some polynomial function f left parenthesis p right parenthesis f ( p ) $f(p)$ . In such results, the assumption of an excluded minor is justified, since we show that analogous results do not hold for the class of 1-planar graphs, which is one of the simplest non-minor-closed monotone classes. In fact, we show that 1-planar graphs do not have tree-decompositions with width within an additive constant of optimal and with bags of bounded treewidth. On the other hand, we show that 1-planar n n $n$ -vertex graphs have tree-decompositions with width upper O left parenthesis StartRoot n EndRoot right parenthesis O ( n ) $O(\sqrt {n})$ (which is the asymptotically tight bound) and with bounded treewidth bags. Moreover, this result holds in the more general setting of bounded layered treewidth, where the union of a bounded number of bags has bounded treewidth.