Face distributions of embeddings of complete graphs

2017/08/07 by Timothy Sun, Sun, Timothy · 4 citations
Computer Science · Mathematics · Engineering · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1708.02092

Abstract

A longstanding open question of Archdeacon and Craft asks whether every complete graph has a minimum genus embedding with at most one nontriangular face. We exhibit such an embedding for each complete graph except K₈, the complete graph on 8 vertices, and we go on to prove that no such embedding can exist for this graph. Our approach also solves a more general problem, giving a complete characterization of the possible face distributions (i.e. the numbers of faces of each length) realizable by minimum genus embeddings of each complete graph. We also tackle analogous questions for nonorientable and maximum genus embeddings.

Cited by

• Settling the genus of the n-prism
• Simultaneous current graph constructions for minimum triangulations and complete graph embeddings
• Revisiting Cases 2 and 11 of the Map Color Theorem
• Revisiting Mayer: Symmetric solutions for sporadic cases of the Map Color Theorem

Related

• Asymptotics of local face distributions and the face distribution of the complete graph
• Genus embeddings of complete graphs minus a matching
• An optimal construction for complete graph embeddings with duals of low connectivity
• Lower bound on the number of the maximum genus embedding of K_n,n
• Face covers and rooted minors in bounded genus graphs