CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
Canadian Mathematical Society
  location:  PublicationsjournalsCJM
Abstract view

Edge-Maximal Graphs on Surfaces

  • Colin McDiarmid,
    Department of Statistics, University of Oxford, United Kingdom
  • David R. Wood,
    School of Mathematical Sciences, Monash University, Melbourne, Australia
Format:   LaTeX   MathJax   PDF  

Abstract

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).
Keywords: graph, surface, embedding graph, surface, embedding
MSC Classifications: 05C10 show english descriptions Planar graphs; geometric and topological aspects of graph theory [See also 57M15, 57M25] 05C10 - Planar graphs; geometric and topological aspects of graph theory [See also 57M15, 57M25]
 

© Canadian Mathematical Society, 2017 : https://cms.math.ca/