Edge-Maximal Graphs on Surfaces
David R. Wood,
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).
graph, surface, embedding
05C10 - Planar graphs; geometric and topological aspects of graph theory [See also 57M15, 57M25]