Minor-Universal Graph for Graphs on Surfaces

We show that, for every n and every surface $\mathrm{\Sigma }$, there is a graph U embeddable on $\mathrm{\Sigma }$ with at most cn^2 vertices that contains as minor every graph embeddable on $\mathrm{\Sigma }$ with n vertices. The constant c depends polynomially on the Euler genus of $\mathrm{\Sigma }$. This generalizes a well-known result for planar graphs due to Robertson, Seymour, and Thomas [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.