Optimal tree-decompositions with bags of bounded treewidth

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 <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:mi>g</mml:mi> </mml:math> $g$ has a tree-decomposition with minimum width such that each bag has treewidth in upper O left parenthesis g right parenthesis <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>g</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> $O(g)$ . This treewidth bound is best possible. Most generally, every upper K Subscript p <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:msub> <mml:mi>K</mml:mi> <mml:mi>p</mml:mi> </mml:msub> </mml:math> $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 <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:mi>f</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>p</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> $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 <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:mi>n</mml:mi> </mml:math> $n$ -vertex graphs have tree-decompositions with width upper O left parenthesis StartRoot n EndRoot right parenthesis <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msqrt> <mml:mi>n</mml:mi> </mml:msqrt> <mml:mo stretchy="false">)</mml:mo> </mml:math> $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.