Title: The Graph Minors Structure Theorem through Bidimensionality Show Chinese title

Title: 通过分治性的图极小结构定理

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 some $(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\mbox{-}\textsf{tw}(G)$ is the minimum $k$ for which $G$ admits a tree-decomposition whose torsos become embeddable embeddable in $\Sigma$ after the removal of a set of dimensionality 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}\mbox{-}\textsf{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}\mbox{-}\textsf{tw}$ cannot be bounded for all parametric graphs in $\mathfrak{D}_{\Sigma}$. Show Chinese abstract

Abstract: 一个图 $G$ 中顶点集合 $X$ 的双维性是最大的 $k$ ，使得 $G$ 包含某个 $(k \times k)$-网格作为 $X$-根的子式。 这种概念允许以下避免使用尖点和涡旋的图极小结构定理(GMST)版本：$K_k$-不可约图是那些具有树分解的图，其每个部分包含有界双维性的集合，移除这些集合后得到的图可以嵌入到某个有界欧拉- genus 的表面上$\Sigma$。我们接下来通过要求$\Sigma$是某个特定的表面来确定目标条件。 这定义了树宽的“表面扩展”，其中$\Sigma\mbox{-}\textsf{tw}(G)$是最小的$k$，使得$G$可以进行树分解，其身体在移除一个维数至多为$k$的集合后可以嵌入到$\Sigma$中。 我们确定了一个有限的参数图集合$\mathfrak{D}_{\Sigma}$，并证明集合$\mathfrak{D}_{\Sigma}$中图的 minor 排除决定了${\Sigma}\mbox{-}\textsf{tw}$在每个曲面$\Sigma.$上的行为。由此可知，集合$\mathfrak{D}_{\Sigma}$与“曲面障碍”对于$\Sigma,$一一对应，即那些在$\Sigma.$中最小不包含的曲面。我们的结果是紧致的，因为${\Sigma}\mbox{-}\textsf{tw}$无法被所有参数图中的$\mathfrak{D}_{\Sigma}$所限制。