2026-07-22T13:16:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19973 2024-06-06T06:21:14Z ddc:004 open_access

Computing Shortest Closed Curves on Non-Orientable Surfaces Bulavka, Denys Colin de Verdière, Éric Fuladi, Niloufar Surface Graph Algorithm Non-orientable surface 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Denys Bulavka and Éric Colin de Verdière and Niloufar Fuladi 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.28 urn:nbn:de:0030-drops-199731 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.28 eng https://creativecommons.org/licenses/by/4.0/legalcode