A New Proof of the Weak Structure Theorem

摘要: We give an elementary and self-contained proof, a numerical improvement, of weaker form the excluded clique minor theorem Robertson Seymour, following. Let $t,r\ge1$ be integers, let $R=49152t^{24}(12t^2+r)$. An $r$-wall is obtained from $2r\times r$-grid by deleting every odd vertical edge in row even row. $G$ graph with no $K_t$ minor, $W$ $R$-wall $G$. prove that there exist set $A\subseteq V(G)$ size at most $12288t^{24}$ $r$-subwall $W'$ such $V(W')\cap A=\emptyset$ flat wall $G-A$ following sense. There exists separation $(X,Y)$ $X\cap Y$ subset vertex cycle $C'$ bounds outer face $W'$, $V(W')\subseteq Y$, $G[Y]$ can almost drawn unit disk vertices on boundary order determined $C'$. Here means assertion holds after repeatedly removing parts separated cutset $Z$ three, adding all edges both ends $Z$. Our proof gives rise to algorithm runs polynomial time when $r$ $t$ are part input instance.