Answers are grounded in this paper and cite their sources.
Shows tree-decompositions with bounded treewidth in various graph classes, implying improved graph analysis techniques.
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ₚ -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(√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.
No takes yet. Share an insight, caveat, or question.
Hendrey et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: