Finding non-orientable surfaces in 3-manifolds

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.
Type de document :
Communication dans un congrès
Sandor Fekete and Anna Lubiw. 32nd International Symposium on Computational Geometry (SoCG 2016), Jun 2016, Boston, United States. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 51, pp.24:1--24:15, 2016, 32nd International Symposium on Computational Geometry (SoCG 2016). 〈10.4230/LIPIcs.SoCG.2016.24〉
Liste complète des métadonnées

http://hal.univ-grenoble-alpes.fr/hal-01355133
Contributeur : Arnaud De Mesmay <>
Soumis le : lundi 22 août 2016 - 14:01:52
Dernière modification le : mardi 10 juillet 2018 - 01:18:26

Identifiants

Collections

Citation

Benjamin A. Burton, Arnaud De Mesmay, Uli Wagner. Finding non-orientable surfaces in 3-manifolds. Sandor Fekete and Anna Lubiw. 32nd International Symposium on Computational Geometry (SoCG 2016), Jun 2016, Boston, United States. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 51, pp.24:1--24:15, 2016, 32nd International Symposium on Computational Geometry (SoCG 2016). 〈10.4230/LIPIcs.SoCG.2016.24〉. 〈hal-01355133〉

Partager

Métriques

Consultations de la notice

211