The sharp asymptotic facial length in girth-saturated plane graphs
For an integer $\ell \ge 3$, consider finite simple graphs with a fixed crossing-free embedding in the plane, of girth at least $\ell$, that are maximal in the following sense: no edge between two nonadjacent vertices can be added to the drawing without crossings while keeping the girth at least $\ell$. A facial cycle is a cycle that forms the whole boundary of a face. Let $F(\ell)$ be the maximum length of a facial cycle over all such embedded graphs, an embedded graph with no facial cycle counting as $0$. A cycle of length $2\ell - 3$ alone shows $F(\ell) \ge 2\ell - 3$. Axenovich, Kießle, Sagdeev and Zhukovskii proved that $F(\ell) = 2\ell - 3$ for $3 \le \ell \le 5$, as Axenovich, Ueckerdt and Weiner had shown for $\ell = 6$, and $$3\ell - 11 \le F(\ell) \le 8\ell - 13 \qquad (\ell \ge 7).$$
Problem. Is $F(\ell) = 3\ell + o(\ell)$ as $\ell \to \infty$?
Source: Axenovich, Kießle, Sagdeev and Zhukovskii (2026), Section 6, Question 1.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Keywords
- AIM Open Applied Problems, girth, graph saturation, plane graphs
References
@article{axenovich2026,
author = {Axenovich, Maria and Kie{\ss}le, Leon and Sagdeev, Arsenii and Zhukovskii, Maksim},
title = {Faces in girth-saturated graphs on surfaces},
journal = {Discrete Comput. Geom.},
volume = {76},
number = {3},
year = {2026},
pages = {1503--1523},
doi = {10.1007/s00454-026-00833-x},
eprint = {2410.13481},
archivePrefix = {arXiv},
}
@article{axenovich2017,
author = {Axenovich, Maria and Ueckerdt, Torsten and Weiner, Pascal},
title = {Splitting planar graphs of girth 6 into two linear forests with short paths},
journal = {J. Graph Theory},
volume = {85},
number = {3},
year = {2017},
pages = {601--618},
doi = {10.1002/jgt.22093},
}
@misc{aim-plane-girth-facial-asymptotic,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{The sharp asymptotic facial length in girth-saturated plane graphs}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/601-plane-girth-facial-asymptotic.md},
note = {Entry 601 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00372, "The sharp asymptotic facial length in girth-saturated plane graphs", clopen.solutions.