Finding non-orientable surfaces in 3-manifolds

Burton, Benjamin A and de Mesmay, Arnaud and Wagner, Uli (2016) Finding non-orientable surfaces in 3-manifolds. In: SoCG: Symposium on Computational Geometry, June 14 - 17, 2016, Boston, MA, USA.

[img] Text
LIPIcs-SoCG-2016-24.pdf - Published Version
Available under License Creative Commons Attribution.
[IST-2016-622-v1+1]
Download (561Kb)
Official URL: http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.24

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.

Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: 3-manifold, Embedding, Low-dimensional topology, Non-orientability, Normal surfaces
Subjects: 500 Science > 510 Mathematics
Research Group: Wagner Group
SWORD Depositor: Sword Import User
Depositing User: Sword Import User
Date Deposited: 21 Jul 2016 07:18
Last Modified: 30 Aug 2017 14:33
URI: https://repository.ist.ac.at/id/eprint/622

Actions (login required)

View Item View Item