Faces in Girth-Saturated Graphs on Surfaces
Discrete & Computational Geometry · 2026-10 · 76 (3) · 1503-1523
DOI: 10.1007/s00454-026-00833-x ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete & Computational Geometry, online erschienen am 09.04.2026. Verfasst von Maria Axenovich und 3 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 34 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Deutsche Forschungsgemeinschaft.
Abstract (Originalsprache)
What is the maximum length $$\textrm{f}_\textrm{max}(\ell , \Sigma )$$ f max ( ℓ , Σ ) of a facial cycle of an inclusion-maximal graph with girth at least $$\ell $$ ℓ embedded on a given surface $$\Sigma $$ Σ ? If $$\Sigma =\mathcal {P}$$ Σ = P is a plane, we show that $$3\ell -11\le \textrm{f}_\textrm{max}(\ell , \mathcal {P})\le 8\ell -13$$ 3 ℓ - 11 ≤ f max ( ℓ , P ) ≤ 8 ℓ - 13 . We also prove that $$\textrm{f}_\textrm{max}(\ell , \Sigma )$$ f max ( ℓ , Σ ) is bounded for any integer $$\ell $$ ℓ and any closed surface $$\Sigma $$ Σ . For a fixed $$\Sigma $$ Σ , we show that $$\Omega (\ell ) =\textrm{f}_\textrm{max}(\ell , \Sigma ) = O(\ell ^2)$$ Ω ( ℓ ) = f max ( ℓ , Σ ) = O ( ℓ 2 ) , while for a fixed $$\ell \ge 6$$ ℓ ≥ 6 , $$\textrm{f}_\textrm{max}(\ell , \Sigma )=\Theta (g)$$ f max ( ℓ , Σ ) = Θ ( g ) , where g is the genus of $$\Sigma $$ Σ .
Förderung
- Deutsche Forschungsgemeinschaft
Zitieren
APA
Axenovich, M., Kießle, L., Sagdeev, A., & Zhukovskii, M. (2026). Faces in Girth-Saturated Graphs on Surfaces. Discrete & Computational Geometry, 76(3), 1503-1523. https://doi.org/10.1007/s00454-026-00833-x
Vancouver
Axenovich M, Kießle L, Sagdeev A, Zhukovskii M. Faces in Girth-Saturated Graphs on Surfaces. Discrete & Computational Geometry. 2026;76(3):1503-1523. doi:10.1007/s00454-026-00833-x
BibTeX
@article{Axenovich2026,
author = {Axenovich, Maria and Kießle, Leon and Sagdeev, Arsenii and Zhukovskii, Maksim},
title = {Faces in Girth-Saturated Graphs on Surfaces},
journal = {Discrete & Computational Geometry},
year = {2026},
volume = {76},
number = {3},
pages = {1503--1523},
doi = {10.1007/s00454-026-00833-x}
}
EUVIMED