Edge-Maximal Graphs on Surfaces

We prove that for every surface $\mathrm{\Sigma }$ of Euler genus $g$, every edge-maximal embedding of a graph in $\mathrm{\Sigma }$ is at most $O(g)$ edges short of a triangulation of $\mathrm{\Sigma }$. This provides the first answer to an open problem of Kainen (1974).