Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

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.
Liste complète des métadonnées

https://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 : mercredi 7 octobre 2020 - 11:22:01

Identifiants

Collections

Citation

Benjamin A. Burton, Arnaud de Mesmay, Uli Wagner. Finding non-orientable surfaces in 3-manifolds. 32nd International Symposium on Computational Geometry (SoCG 2016), Jun 2016, Boston, United States. pp.24:1--24:15, ⟨10.4230/LIPIcs.SoCG.2016.24⟩. ⟨hal-01355133⟩

Partager

Métriques

Consultations de la notice

298