2024/10/17 by Maria Axenovich, Axenovich, Maria, Leon Kießle +4 · 1 citation
Computer Science · #05C10 #05C35 #57M15 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Graph Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.2410.13481
openalex publication_date 2024/10/17 · openalex created_date 2024/10/21 · openalex updated_date 2026/07/28
What is the maximum length \rm f\rm max(ℓ, Σ) of a facial cycle of an inclusion-maximal graph with girth at least ℓ embedded on a given surface Σ? If Σ=P is a plane, we show that 3ℓ-11≤ \rm f\rm max(ℓ, P)≤ 8ℓ-13. We also prove that \rm f\rm max(ℓ, Σ) is bounded for any integer ℓ and any closed surface Σ. For a fixed Σ, we show that Ω(ℓ) =\rm f\rm max(ℓ, Σ) = O(ℓ2), while for a fixed ℓ≥ 6, \rm f\rm max(ℓ, Σ)=Θ(g), where g is the genus of Σ.