EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Faces in Girth-Saturated Graphs on Surfaces

Maria Axenovich, Leon Kießle, Arsenii Sagdeev, Maksim Zhukovskii

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →