Computing shortest closed curves on non-orientable surfaces
<|reference_start|>Computing shortest closed curves on non-orientable surfaces: We initiate the study of computing shortest non-separating simple closed curves with some given topological properties on non-orientable surfaces. While, for orientable surfaces, any two non-separating simple closed curves are related by a self-homeomorphism of the surface, and computing shortest such curves has been vastly studied, for non-orientable ones the classification of non-separating simple closed curves up to ambient homeomorphism is subtler, depending on whether the curve is one-sided or two-sided, and whether it is orienting or not (whether it cuts the surface into an orientable one).   We prove that computing a shortest orienting (weakly) simple closed curve on a non-orientable combinatorial surface is NP-hard but fixed-parameter tractable in the genus of the surface. In contrast, we can compute a shortest non-separating non-orienting (weakly) simple closed curve with given sidedness in $g^{O(1)}.n\log n$ time, where $g$ is the genus and $n$ the size of the surface.   For these algorithms, we develop tools that can be of independent interest, to compute a variation on canonical systems of loops for non-orientable surfaces based on the computation of an orienting curve, and some covering spaces that are essentially quotients of homology covers.<|reference_end|>
@article{bulavka2024computing,
    title={Computing shortest closed curves on non-orientable surfaces},
    author={Denys Bulavka and 'Eric Colin de Verdi`ere and Niloufar Fuladi},
    journal={arXiv preprint arXiv:2403.11749},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.11749},
    primaryClass={cs.CG cs.CC math.GT}
}