2026-07-24T10:14:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5916 2024-03-06T10:37:16Z ddc:004 open_access

Finding Non-Orientable Surfaces in 3-Manifolds Burton, Benjamin A. de Mesmay, Arnaud Wagner, Uli 3-manifold low-dimensional topology embedding non-orientability normal surfaces We investigate the complexity of finding an embedded non-orientable surface of Euler genus g in a triangulated 3-manifold. This problem occurs both as a natural question in low-dimensional topology, and as a first non-trivial instance of embeddability of complexes into 3-manifolds. We prove that the problem is NP-hard, thus adding to the relatively few hardness results that are currently known in 3-manifold topology. In addition, we show that the problem lies in NP when the Euler genus g is odd, and we give an explicit algorithm in this case. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benjamin A. Burton and Arnaud de Mesmay and Uli Wagner 2016 Is Part Of LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2016.24 urn:nbn:de:0030-drops-59168 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.24 eng https://creativecommons.org/licenses/by/3.0/legalcode