Finding non-orientable surfaces in 3-manifolds Conference Paper


Author(s): Burton, Benjamin A; de Mesmay, Arnaud; Wagner, Uli
Title: Finding non-orientable surfaces in 3-manifolds
Title Series: LIPIcs
Affiliation IST Austria
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.
Keywords: 3-manifold; Embedding; Low-dimensional topology; Non-orientability; Normal surfaces
Conference Title: SoCG: Symposium on Computational Geometry
Volume: 51
Conference Dates: June 14 - 17, 2016
Conference Location: Boston, MA, USA
ISBN: 978-1-4503-2594-3
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik  
Date Published: 2016-06-01
Start Page: 24.1
End Page: 24.15
Copyright Statement: CC-BY
URL:
DOI: 10.4230/LIPIcs.SoCG.2016.24
Notes: We would like to thank Saul Schleimer and Eric Sedgwick for stimulating discussions, and the anonymous reviewers for helpful comments. The first author is supported by the Australian Research Council (project DP140104246). † The second author has received funding from the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013) under REA grant agreement no. 291734.
Open access: yes (OA journal)
IST Austria Authors
  1. Uli Wagner
    43 Wagner
Related IST Austria Work