---
_id: '534'
abstract:
- lang: eng
text: 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.
article_processing_charge: No
article_type: original
author:
- first_name: Benjamin
full_name: Burton, Benjamin
last_name: Burton
- first_name: Arnaud N
full_name: De Mesmay, Arnaud N
id: 3DB2F25C-F248-11E8-B48F-1D18A9856A87
last_name: De Mesmay
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: 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
apa: Burton, B., de Mesmay, A. N., & Wagner, U. (2017). Finding non-orientable
surfaces in 3-Manifolds. Discrete & Computational Geometry. Springer.
https://doi.org/10.1007/s00454-017-9900-0
chicago: Burton, Benjamin, Arnaud N de Mesmay, and Uli Wagner. “Finding Non-Orientable
Surfaces in 3-Manifolds.” Discrete & Computational Geometry. Springer,
2017. https://doi.org/10.1007/s00454-017-9900-0.
ieee: B. Burton, A. N. de Mesmay, and U. Wagner, “Finding non-orientable surfaces
in 3-Manifolds,” Discrete & Computational Geometry, vol. 58, no. 4.
Springer, pp. 871–888, 2017.
ista: Burton B, de Mesmay AN, Wagner U. 2017. Finding non-orientable surfaces in
3-Manifolds. Discrete & Computational Geometry. 58(4), 871–888.
mla: 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.
short: B. Burton, A.N. de Mesmay, U. Wagner, Discrete & Computational Geometry
58 (2017) 871–888.
date_created: 2018-12-11T11:47:01Z
date_published: 2017-06-09T00:00:00Z
date_updated: 2023-02-21T17:01:34Z
day: '09'
department:
- _id: UlWa
doi: 10.1007/s00454-017-9900-0
external_id:
arxiv:
- '1602.07907'
intvolume: ' 58'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1602.07907
month: '06'
oa: 1
oa_version: Preprint
page: 871 - 888
publication: Discrete & Computational Geometry
publication_identifier:
issn:
- '01795376'
publication_status: published
publisher: Springer
publist_id: '7283'
quality_controlled: '1'
related_material:
record:
- id: '1379'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Finding non-orientable surfaces in 3-Manifolds
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 58
year: '2017'
...