Quickly excluding a non-planar graph
share
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× 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, J. Combin. Theory Ser. B 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.
READ FULL TEXT