Hostname: page-component-7b7567c8c-9cwtv Total loading time: 0 Render date: 2026-11-19T08:05:01.902Z Has data issue: false hasContentIssue false

Edge-Maximal Graphs on Surfaces

Published online by Cambridge University Press:  20 November 2018

Colin McDiarmid
Affiliation:
Department of Statistics, University of Oxford, United Kingdom email: cmcd@stats.ox.ac.uk
David R. Wood
Affiliation:
Department of Statistics, University of Oxford, United Kingdom email: cmcd@stats.ox.ac.uk
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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).

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 2018