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

We 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