Edge-Maximal Graphs on Surfaces
  We prove that for every surface $\Sigma$ of Euler genus $g$, every edge-maximal embedding of a graph in $\Sigma$ is at most $O(g)$ edges short of a triangulation of $\Sigma$. This provides the first answer to an open problem of Kainen (1974). 
Colin McDiarmid and David R. Wood
math.CO