  We study edge-maximal, non-complete graphs on surfaces that do not
triangulate the surface. We prove that there is no such graph on the projective
plane $\mathbb{N}_1$, $K_7-e$ is the unique such graph on the Klein bottle
$\mathbb{N}_2$ and $K_8-E(C_5)$ is the unique such graph on the torus
$\mathbb{S}_1$. In contrast to this for each $g\ge 2$ we construct an infinite
family of such graphs on the orientable surface $\mathbb{S}_g$ of genus $g$,
that are $\lfloor \frac{g}{2} \rfloor$ edges short of a triangulation.
