Excluding Surfaces as Minors in Graphs

arXiv2306.01724MaRDI QIDQ6510399FDOQ6510399

Authors: Dimitrios M. Thilikos, Sebastian Wiederrecht 

Abstract: We introduce an annotated extension of treewidth that measures the contribution of a vertex set $X$ to the treewidth of a graph $G.$ This notion provides a graph distance measure to some graph property $mathcalP$: A vertex set $X$ is a $k$-treewidth modulator of $G$ to $mathcalP$ if the treewidth of $X$ in $G$ is at most $k$ and its removal gives a graph in $mathcalP.$This notion allows for a version of the Graph Minors Structure Theorem (GMST) that has no need for apices and vortices: $K_k$-minor free graphs are those that admit tree-decompositions whose torsos have $c_k$-treewidth modulators to some surface of Euler-genus $c_k.$ This reveals that minor-exclusion is essentially tree-decomposability to a ``modulator-target scheme where the modulator is measured by its treewidth and the target is surface embeddability. We then fix the target condition by demanding that $Sigma$ is some particular surface and define a ``surface extension of treewidth, where $Sigmambox-mathsftw(G)$ is the minimum $k$ for which $G$ admits a tree-decomposition whose torsos have a $k$-treewidth modulator to being embeddable in $Sigma.$We identify a finite collection $mathfrak{D}_{Sigma}$ of parametric graphs and prove that the minor-exclusion of the graphs in $mathfrak{D}_{Sigma}$ precisely determines the asymptotic behavior of $Sigmambox-mathsftw,$ 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.$

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75) Graph minors (05C83)

This page was built for publication: Excluding Surfaces as Minors in Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6510399)