Faces in girth-saturated graphs on surfaces

Abstract

What is the maximum length ${\mathrm{f}}_{\max }(\ell ,\hat{I}\pounds )$ of a facial cycle of an inclusion-maximal graph with girth at least $\ell$ embedded on a given surface $\hat{I}\pounds$? If $\hat{I}\pounds =\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 ,\hat{I}\pounds )$ is bounded for any integer $\ell$ and any closed surface $\hat{I}\pounds$. For a fixed $\hat{I}\pounds$, we show that $\hat{I}\text{c◯}(\ell )={\mathrm{f}}_{\max }(\ell ,\hat{I}\pounds )=O({\ell }^2)$, while for a fixed $\ell \ge 6$, ${\mathrm{f}}_{\max }(\ell ,\hat{I}\pounds )=\hat{I}˜(g)$, where $g$ is the genus of $\hat{I}\pounds$.

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