KIT | KIT-Bibliothek | Impressum | Datenschutz

Faces in Girth-Saturated Graphs on Surfaces

Axenovich, Maria 1; Kießle, Leon; Sagdeev, Arsenii 1; Zhukovskii, Maksim
1 Institut für Algebra und Geometrie (IAG), Karlsruher Institut für Technologie (KIT)

Abstract:

What is the maximum length f$_{max}$($\ell$, $\Sigma$) of a facial cycle of an inclusion-maximal graph with girth at least $\ell$ embedded on a given surface $\Sigma$? If $\Sigma$ = $P$ is a plane, we show that 3$\ell$ − 11 ≤ f$_{max}$($\ell$,$P$) ≤ 8$\ell$ − 13. We also prove that f$_{max}$($\ell$, $\Sigma$ ) is bounded for any integer $\ell$ and any closed surface $\Sigma$. For a fixed $\Sigma$, we show that $\Omega$($\ell$) = f$_{max}$($\ell$, $\Sigma$) = $O$($\ell$$^2$), while for a fixed $\ell$≥ 6, f$_{max}$($\ell$, $\Sigma$) = $\Theta$(g), where g is
the genus of $\Sigma$.


Download
Originalveröffentlichung
DOI: 10.1007/s00454-026-00833-x
Zugehörige Institution(en) am KIT Institut für Algebra und Geometrie (IAG)
Publikationstyp Zeitschriftenaufsatz
Publikationsjahr 2026
Sprache Englisch
Identifikator ISSN: 0179-5376, 1432-0444
KITopen-ID: 1000192540
Erschienen in Discrete and Computational Geometry
Verlag Springer
Seiten 1
Vorab online veröffentlicht am 09.04.2026
Externe Relationen Siehe auch
Schlagwörter Planar graph, Plane graph, Surface, Genus, Girth, Face length, Saturation, Turan theorem
Nachgewiesen in Web of Science
OpenAlex
Scopus
KIT – Die Universität in der Helmholtz-Gemeinschaft
KITopen Landing Page