标题： 排除曲面作为图的子式 显示英文标题

标题： Excluding Surfaces as Minors in Graphs

摘要： 我们引入了一个关于树宽的注释扩展，它衡量顶点集$X$对图$G.$的树宽的贡献。这一概念提供了一种到某些图性质$\mathcal{P}$的图距离度量：如果图$X$在$G$中的树宽最多为$k$，并且其删除给出一个在$\mathcal{P}.$中的图，则顶点集$X$是图$G$到$\mathcal{P}$的$k$-树宽调节器。这一概念允许一种无需尖峰和涡旋的图极小结构定理（GMST）版本：$K_k$-子图自由图是那些具有树分解的图，其每个部分在某个欧拉-亏格表面$c_{k}.$上有$c_{k}$-树宽调节器。这揭示了子图排除本质上是到“调节器目标方案”的树分解性，其中调节器通过其树宽来衡量，而目标是表面可嵌入性。 我们然后通过要求$\Sigma$是某个特定的曲面来确定目标条件，并定义一个“曲面扩展”的宽度，其中$\Sigma\mbox{-}\mathsf{tw}(G)$是最小的$k$，使得$G$允许一个树分解，其骨结构对于被嵌入$\Sigma.$有$k$-宽度调节器。我们识别出一个有限的参数图集合$\mathfrak{D}_{\Sigma}$并证明$\mathfrak{D}_{\Sigma}$中的图的极小排除精确地决定了${\Sigma}\mbox{-}\mathsf{tw},$对于每个曲面$\Sigma.$的渐近行为。由此得出，集合$\mathfrak{D}_{\Sigma}$与“曲面障碍”对于$\Sigma,$一一对应，即那些在$\Sigma.$中最小不包含的曲面。 显示英文摘要

摘要： 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 $\mathcal{P}$: A vertex set $X$ is a $k$-treewidth modulator of $G$ to $\mathcal{P}$ if the treewidth of $X$ in $G$ is at most $k$ and its removal gives a graph in $\mathcal{P}.$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 $\Sigma\mbox{-}\mathsf{tw}(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 ${\Sigma}\mbox{-}\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.$