On the largest planar graphs with everywhere positive combinatorial curvature (extended arxiv version)

Abstract

A planar PCC graph is a simple connected planar graph with everywhere positive combinatorial curvature which is not a prism or an antiprism and with all vertices of degree at least 3. We prove that every planar PCC graph has at most 208 vertices, thus answering completely a question raised by DeVos and Mohar. The proof is based on a refined discharging technique and on an accurate low-scale combinatorical description of such graphs. We also prove that all faces in a planar PCC graph have at most 41 sides, and this result is sharp as well.

63 pages, 72 figures, 23 tables. Modifications from the previous arxiv version: expanded the bibliography, improved the introduction, improved the remarks on the method (Sec 3.1), added heuristics for the discharging function (Sec 4.7), added corollary for projective PCC graphs, updated the acknowledgements section, corrected minor typos

Cited by in corpus (6)

• Sharp isoperimetric inequalities for infinite plane graphs with bounded vertex and face degrees
• A curvature notion for planar graphs stable under planar duality
• Areas of spherical polyhedral surfaces with regular faces
• Combinatorial, Bakry-Émery, Ollivier's Ricci curvature notions and their motivation from Riemannian geometry
• The set of vertices with positive curvature in a planar graph with nonnegative curvature
• On the size of planar graphs with positive Lin-Lu-Yau Ricci curvature