Finding non-orientable surfaces in 3-Manifolds

B. Burton, A.N. De Mesmay, U. Wagner, Discrete & Computational Geometry 58 (2017) 871–888.


Journal Article | Published | English

Scopus indexed
Department
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.
Publishing Year
Date Published
2017-06-09
Journal Title
Discrete & Computational Geometry
Volume
58
Issue
4
Page
871 - 888
ISSN
IST-REx-ID
534

Cite this

Burton B, De Mesmay AN, Wagner U. Finding non-orientable surfaces in 3-Manifolds. Discrete & Computational Geometry. 2017;58(4):871-888. doi:10.1007/s00454-017-9900-0
Burton, B., De Mesmay, A. N., & Wagner, U. (2017). Finding non-orientable surfaces in 3-Manifolds. Discrete & Computational Geometry, 58(4), 871–888. https://doi.org/10.1007/s00454-017-9900-0
Burton, Benjamin, Arnaud N De Mesmay, and Uli Wagner. “Finding Non-Orientable Surfaces in 3-Manifolds.” Discrete & Computational Geometry 58, no. 4 (2017): 871–88. https://doi.org/10.1007/s00454-017-9900-0.
B. Burton, A. N. De Mesmay, and U. Wagner, “Finding non-orientable surfaces in 3-Manifolds,” Discrete & Computational Geometry, vol. 58, no. 4, pp. 871–888, 2017.
Burton B, De Mesmay AN, Wagner U. 2017. Finding non-orientable surfaces in 3-Manifolds. Discrete & Computational Geometry. 58(4), 871–888.
Burton, Benjamin, et al. “Finding Non-Orientable Surfaces in 3-Manifolds.” Discrete & Computational Geometry, vol. 58, no. 4, Springer, 2017, pp. 871–88, doi:10.1007/s00454-017-9900-0.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access
Material in IST:
Earlier Version

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1602.07907

Search this title in

Google Scholar