KIT | KIT-Bibliothek | Impressum | Datenschutz

Faces in Girth-Saturated Graphs on Surfaces

Axenovich, Maria 1; Kießle, Leon 2; Sagdeev, Arsenii 1; Zhukovskii, Maksim
1 Institut für Algebra und Geometrie (IAG), Karlsruher Institut für Technologie (KIT)
2 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
Scopus
OpenAlex
Relationen in KITopen
KIT – Die Universität in der Helmholtz-Gemeinschaft
KITopen Landing Page