Edge-Maximal Graphs on Surfaces

Colin McDiarmid, David R Wood

Research output: Contribution to journalArticleResearchpeer-review

3 Citations (Scopus)

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 ∑. 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
Volume70
Issue number4
DOIs
Publication statusPublished - 1 Aug 2018

Keywords

  • Embedding
  • Graph
  • Surface

Cite this