Edge-maximal graphs on surfaces
We prove that for every surface Σ of Euler genus g, every edgemaximal 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).
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Published: |
Canadian Mathematical Society
2017
|