2023/06/02 by Thilikos, Dimitrios M., Wiederrecht, Sebastian
#05C10 #05C75 #05C83 #68R10 #Combinatorics (math.CO) #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.2306.01724
The bidimensionality of a set of vertices X in a graph G is the maximum k for which G contains as a X-rooted minor some (k × k)-grid. This notion allows for the following version of the Graph Minors Structure Theorem (GMST) that avoids the use of apices and vortices: Kk-minor free graphs are those that admit tree-decompositions whose torsos contain sets of bounded bidimensionality whose removal yield a graph embeddable in some surface Σ of bounded Euler-genus. We next fix the target condition by demanding that Σ is some particular surface. This defines a "surface extension" of treewidth, where Σ-\textsftw(G) is the minimum k for which G admits a tree-decomposition whose torsos become embeddable embeddable in Σ after the removal of a set of dimensionality at most k. We identify a finite collection \mathfrakDΣ of parametric graphs and prove that the minor-exclusion of the graphs in \mathfrakDΣ determines the behavior of Σ-\textsftw, for every surface Σ. It follows that the collection \mathfrakDΣ bijectively corresponds to the "surface obstructions" for Σ, i.e., surfaces that are minimally non-contained in Σ. Our results are tight in the sense that Σ-\textsftw cannot be bounded for all parametric graphs in \mathfrakDΣ.