Minor-Universal Graph for Graphs on Surfaces

We show that, for every $n$ and every surface $\Sigma$ (orientable or not), there is a graph $U$ embeddable on $\Sigma$ with at most $c n^2$ vertices that contains as minor every graph embeddable on $\Sigma$ with
$n$ vertices. The constant $c$ depends polynomially on the Euler genus of $\Sigma$. This generalizes a well-known result for planar graphs due to Robertson, Seymour, and Thomas [\textit{Quickly Excluding a Planar
Graph.} J. Comb. Theory B, 1994] which states that the square grid on $4n^2$ vertices contains as minor every planar graph with $n$ vertices.
This is a joint work with Cyril Gavoille.

Everyone is welcome and encouraged to attend.