Finding non-orientable surfaces in 3-manifolds

Burton, Benjamin A., de Mesmay, Arnaud and Wagner, Uli (2016). Finding non-orientable surfaces in 3-manifolds. In: Sandor Fekete and Anna Lubiw, 32nd International Symposium on Computational Geometry (SoCG 2016). International Symposium on Computational Geometry, Boston, MA, United States, (24:1-24:15). 14-17 June 2016. doi:10.4230/LIPIcs.SoCG.2016.24

Author Burton, Benjamin A.
de Mesmay, Arnaud
Wagner, Uli
Title of paper Finding non-orientable surfaces in 3-manifolds
Conference name International Symposium on Computational Geometry
Conference location Boston, MA, United States
Conference dates 14-17 June 2016
Proceedings title 32nd International Symposium on Computational Geometry (SoCG 2016)   Check publisher's open access policy
Journal name Leibniz International Proceedings in Informatics, LIPIcs   Check publisher's open access policy
Place of Publication Wadern, Germany
Publisher Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Publication Year 2016
Year available 2017
Sub-type Fully published paper
DOI 10.4230/LIPIcs.SoCG.2016.24
Open Access Status DOI
ISBN 9783959770095
ISSN 1868-8969
Editor Sandor Fekete
Anna Lubiw
Volume 51
Issue 4
Start page 24:1
End page 24:15
Total pages 15
Language eng
Abstract/Summary 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.
Keyword 3-manifold
Low-dimensional topology
Normal surfaces
Q-Index Code E1
Q-Index Status Provisional Code
Grant ID 291734
Institutional Status UQ

Document type: Conference Paper
Sub-type: Discrete & Computational Geometry
Collections: School of Mathematics and Physics
HERDC Pre-Audit
Version Filter Type
Citation counts: Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Created: Wed, 15 Jun 2016, 15:34:39 EST by Dr Benjamin Burton on behalf of Mathematics