Edge-Maximal Graphs on Surfaces
Colin McDiarmid, David R. Wood · Canadian Journal of Mathematics · 2017
Abstract We prove that for every surface ∑ of Euler genus g, every edge-maximal embedding of a graph in ∑ is at most O(g) edges short of a triangulation of ∑. This provides the first answer to an open problem of Kainen (1974).