DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2024.28

Computing Shortest Closed Curves on Non-Orientable Surfaces

Authors: Denys Bulavka, Éric Colin de Verdière, and Niloufar Fuladi

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract

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.

Cite as

Denys Bulavka, Éric Colin de Verdière, and Niloufar Fuladi. Computing Shortest Closed Curves on Non-Orientable Surfaces. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bulavka_et_al:LIPIcs.SoCG.2024.28,
  author =	{Bulavka, Denys and Colin de Verdi\`{e}re, \'{E}ric and Fuladi, Niloufar},
  title =	{{Computing Shortest Closed Curves on Non-Orientable Surfaces}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.28},
  URN =		{urn:nbn:de:0030-drops-199731},
  doi =		{10.4230/LIPIcs.SoCG.2024.28},
  annote =	{Keywords: Surface, Graph, Algorithm, Non-orientable surface}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2022.41

Short Topological Decompositions of Non-Orientable Surfaces

Authors: Niloufar Fuladi, Alfredo Hubard, and Arnaud de Mesmay

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract

We investigate short topological decompositions of non-orientable surfaces and provide algorithms to compute them. Our main result is a polynomial-time algorithm that for any graph embedded in a non-orientable surface computes a canonical non-orientable system of loops so that any loop from the canonical system intersects any edge of the graph in at most 30 points. The existence of such short canonical systems of loops was well known in the orientable case and an open problem in the non-orientable case. Our proof techniques combine recent work of Schaefer-Štefankovič with ideas coming from computational biology, specifically from the signed reversal distance algorithm of Hannenhalli-Pevzner. This result confirms a special case of a conjecture of Negami on the joint crossing number of two embeddable graphs. We also provide a correction for an argument of Negami bounding the joint crossing number of two non-orientable graph embeddings.

Cite as

Niloufar Fuladi, Alfredo Hubard, and Arnaud de Mesmay. Short Topological Decompositions of Non-Orientable Surfaces. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fuladi_et_al:LIPIcs.SoCG.2022.41,
  author =	{Fuladi, Niloufar and Hubard, Alfredo and de Mesmay, Arnaud},
  title =	{{Short Topological Decompositions of Non-Orientable Surfaces}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{41:1--41:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.41},
  URN =		{urn:nbn:de:0030-drops-160492},
  doi =		{10.4230/LIPIcs.SoCG.2022.41},
  annote =	{Keywords: Computational topology, embedded graph, non-orientable surface, joint crossing number, canonical system of loop, surface decomposition}
}

Search Results

Documents authored by Fuladi, Niloufar

Computing Shortest Closed Curves on Non-Orientable Surfaces

Abstract

Cite as

Short Topological Decompositions of Non-Orientable Surfaces

Abstract

Cite as

Thanks for your feedback!

Could not send message