On Short Noncontractible Cycles in Embedded Graphs
Joan P. Hutchinson · SIAM Journal on Discrete Mathematics · 1988
This paper contains a proof that every triangulation of an orientable surface of genus $g > 1$ with n vertices contains a noncontractible cycle of length $O( \sqrt{n/g} \log g )$. These bounds are tighter than those previously known, but are not the conjectured optimal. These results and techniques are related to “planarizing” problems in which a small set of vertices is sought whose removal leaves a planar graph and to “separator” problems in which a small set of vertices is sought whose removal leaves a graph with all components small.