The Graph Minor Structure Theorem through Bidimensionality

Abstract

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 the $(k\times k)$-grid. This notion allows for the following version of the Graph Minors Structure Theorem (GMST) that avoids the use of apices and vortices: $K_k$-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 $\Sigma$ of bounded Euler-genus. We next fix the target condition by demanding that $\Sigma$ is some particular surface. This defines a "surface extension" of treewidth, where $\Sigma$-$\mathsf{tw}$ is the minimum $k$ for which $G$ admits a tree decomposition whose torsos become embeddable in $\Sigma$ after the removal of a set of bidimensionality at most $k$. We identify a finite collection ${\mathfrak{D}}_{\Sigma }$ of parametric graphs and prove that the minor-exclusion of the graphs in ${\mathfrak{D}}_{\Sigma }$ determines the behavior of $\Sigma$-$\mathsf{tw},$ for every surface $\Sigma .$ It follows that the collection ${\mathfrak{D}}_{\Sigma }$ bijectively corresponds to the "surface obstructions" for $\Sigma ,$ i.e., surfaces that are minimally non-contained in $\Sigma .$ Our results are tight in the sense that $\Sigma$-$\mathsf{tw}$ cannot be bounded for all parametric graphs in ${\mathfrak{D}}_{\Sigma }$.

arXiv commentWe split the article into two volumes. The first volume, concerned with extracting surfaces from the GMST, has become the new version of this article, while the second volume will be a different upload. arXiv admin note: text overlap with arXiv:2304.04517