论文标题
快速排除非平面图
Quickly excluding a non-planar graph
论文作者
论文摘要
Robertson和Seymour的图形未成年人和Seymour的基石定理是每个图$ G $没有固定图$ H $的较小同构的每个图$ G $具有一定的结构。然后可以利用结构来推断深远的后果。 The exact statement requires some explanation, but roughly it says that there exist integers $k,n$ depending on $H$ only such that $0<k<n$ and for every $n\times n$ grid minor $J$ of $G$ the graph $G$ has a a $k$-near embedding in a surface $Σ$ that does not embed $H$ in such a way that a substantial part of $J$ is embedded in $Σ$. Here a $k$-near embedding means that after deleting at most $k$ vertices the graph can be drawn in $Σ$ without crossings, except for local areas of non-planarity, where crossings are permitted, but at most $k$ of these areas are attached to the rest of the graph by four or more vertices and inside those the graph is constrained in a different way, again depending on the parameter $k$. 到目前为止，原始和唯一的证明很长，并且使用了Graph Finors系列中开发的许多结果。我们提供的证明仅使用我们的早期论文[平壁定理的新证明，{\ it J. 我们的证明具有建设性，并产生多项式时间算法来构建这种结构。我们还为结构定理提供了明确的常数，而原始证明仅保证存在这种常数。
A cornerstone theorem in the Graph Minors series of Robertson and Seymour is the result that every graph $G$ with no minor isomorphic to a fixed graph $H$ has a certain structure. The structure can then be exploited to deduce far-reaching consequences. The exact statement requires some explanation, but roughly it says that there exist integers $k,n$ depending on $H$ only such that $0<k<n$ and for every $n\times n$ grid minor $J$ of $G$ the graph $G$ has a a $k$-near embedding in a surface $Σ$ that does not embed $H$ in such a way that a substantial part of $J$ is embedded in $Σ$. Here a $k$-near embedding means that after deleting at most $k$ vertices the graph can be drawn in $Σ$ without crossings, except for local areas of non-planarity, where crossings are permitted, but at most $k$ of these areas are attached to the rest of the graph by four or more vertices and inside those the graph is constrained in a different way, again depending on the parameter $k$. The original and only proof so far is quite long and uses many results developed in the Graph Minors series. We give a proof that uses only our earlier paper [A new proof of the flat wall theorem, {\it J.~Combin.\ Theory Ser.\ B \bf 129} (2018), 158--203] and results from graduate textbooks. Our proof is constructive and yields a polynomial time algorithm to construct such a structure. We also give explicit constants for the structure theorem, whereas the original proof only guarantees the existence of such constants.
