Faces in girth-saturated graphs on surfaces

Abstract

What is the maximum length ${\mathrm{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 =\mathcal{P}$ is a plane, we show that $3\ell -11\le {\mathrm{f}}_{\max }(\ell ,\mathcal{P})\le 8\ell -13$. We also prove that ${\mathrm{f}}_{\max }(\ell ,\Sigma )$ is bounded for any integer $\ell$ and any closed surface $\Sigma$. For a fixed $\Sigma$, we show that $\Omega (\ell )={\mathrm{f}}_{\max }(\ell ,\Sigma )=O({\ell }^2)$, while for a fixed $\ell \ge 6$, ${\mathrm{f}}_{\max }(\ell ,\Sigma )=\Theta (g)$, where $g$ is the genus of $\Sigma$.

arXiv comment16 pages, 22 figures; major revision: improved upper bound for closed surfaces