Polynomial bounds for the Graph Minor Structure Theorem

The Graph Minor Structure Theorem, originally proven by Robertson and Seymour [JCTB, 2003], asserts that there exist functions f 1 , f 2 : N → N such that for every non-planar graph H with t := |V (H)|, every H-minor-free graph can be obtained via the clique-sum operation from graphs which embed into surfaces where H does not embed after deleting at most f 1 (t) many vertices with up to at most t 2 -1 many "vortices" which are of "depth" at most f 2 (t). In the proof presented by Robertson and Seymour the functions f 1 and f 2 are non-constructive. Kawarabayashi, Thomas, and Wollan [arXiv, 2020] found a new proof showing that f 1 (t), f 2 (t) ∈ 2 poly(t) . While believing that this bound was the best their methods could achieve, Kawarabayashi, Thomas, and Wollan conjectured that f 1 and f 2 can be improved to be polynomials.

In this paper we confirm their conjecture and prove that f 1 (t), f 2 (t) ∈ O(t 2300 ). Our proofs are fully constructive and yield a polynomial-time algorithm that either finds H as a minor in a graph G or produces a clique-sum decomposition for G as above.