Edge-Maximal Graphs on Surfaces

Colin McDiarmid, David R Wood

Research output: Contribution to journalArticleResearchpeer-review

4 Citations (Scopus)


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 ∑. Ths provides the first answer to an open problem of Kainen (1974).
Original languageEnglish
Article number028
Pages (from-to)925-942
Number of pages18
JournalCanadian Journal of Mathematics
Issue number4
Publication statusPublished - 1 Aug 2018


  • Embedding
  • Graph
  • Surface

Cite this