2023/05/11 by Cyril Gavoille, Claire Hilaire, Gavoille, Cyril +1 · 2 citations
#cs.DM
paper · pdf · doi:10.48550/arxiv.2305.06673
We show that for integer every n and every surface Σ, there is a graph embeddable on Σ with at most c n2 vertices that contains as a minor every n-vertex graph embeddable on Σ. The constant c depends polynomially on the Euler genus of Σ. This generalizes a well-known result for planar graphs by Robertson, Seymour, and Thomas [Quickly Excluding a Planar Graph. J. Comb. Theory B, 1994], which states that the square grid on 4n2 vertices contains as a minor every n-vertex planar graph, an important step in showing that graphs excluding that graphs excluding a planar graph as a minor have bounded tree-width. According to Gorsky, Seweryn, and Wiederrecht [Polynomial Bounds for the Graph Minor Structure Theorem, FOCS '25], our construction provides the final key ingredient in the search for polynomial bounds in the decomposition of graphs excluding as minor a given n-vertex graph achieving tight bounds with respect to the Euler genus of the surface part.