@inproceedings{1379, abstract = {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.}, author = {Burton, Benjamin and De Mesmay, Arnaud N and Wagner, Uli}, location = {Medford, MA, USA}, pages = {24.1 -- 24.15}, publisher = {Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing}, title = {{Finding non-orientable surfaces in 3-manifolds}}, doi = {10.4230/LIPIcs.SoCG.2016.24}, volume = {51}, year = {2016}, }