---
_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
arxiv: 1
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'
...
---
_id: '1379'
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.
alternative_title:
- LIPIcs
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.
In: Vol 51. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing;
2016:24.1-24.15. doi:10.4230/LIPIcs.SoCG.2016.24'
apa: 'Burton, B., de Mesmay, A. N., & Wagner, U. (2016). Finding non-orientable
surfaces in 3-manifolds (Vol. 51, p. 24.1-24.15). Presented at the SoCG: Symposium
on Computational Geometry, Medford, MA, USA: Schloss Dagstuhl- Leibniz-Zentrum
fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2016.24'
chicago: Burton, Benjamin, Arnaud N de Mesmay, and Uli Wagner. “Finding Non-Orientable
Surfaces in 3-Manifolds,” 51:24.1-24.15. Schloss Dagstuhl- Leibniz-Zentrum fur
Informatik GmbH, Dagstuhl Publishing, 2016. https://doi.org/10.4230/LIPIcs.SoCG.2016.24.
ieee: 'B. Burton, A. N. de Mesmay, and U. Wagner, “Finding non-orientable surfaces
in 3-manifolds,” presented at the SoCG: Symposium on Computational Geometry, Medford,
MA, USA, 2016, vol. 51, p. 24.1-24.15.'
ista: 'Burton B, de Mesmay AN, Wagner U. 2016. Finding non-orientable surfaces in
3-manifolds. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 51, 24.1-24.15.'
mla: Burton, Benjamin, et al. Finding Non-Orientable Surfaces in 3-Manifolds.
Vol. 51, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing,
2016, p. 24.1-24.15, doi:10.4230/LIPIcs.SoCG.2016.24.
short: B. Burton, A.N. de Mesmay, U. Wagner, in:, Schloss Dagstuhl- Leibniz-Zentrum
fur Informatik GmbH, Dagstuhl Publishing, 2016, p. 24.1-24.15.
conference:
end_date: 2016-06-17
location: Medford, MA, USA
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2016-06-14
date_created: 2018-12-11T11:51:41Z
date_published: 2016-06-01T00:00:00Z
date_updated: 2023-02-23T12:23:20Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2016.24
file:
- access_level: open_access
checksum: f04248a61c24297cfabd30c5f8e0deb9
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:12:12Z
date_updated: 2020-07-14T12:44:47Z
file_id: '4930'
file_name: IST-2016-622-v1+1_LIPIcs-SoCG-2016-24.pdf
file_size: 574770
relation: main_file
file_date_updated: 2020-07-14T12:44:47Z
has_accepted_license: '1'
intvolume: ' 51'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 24.1 - 24.15
publication_status: published
publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
publist_id: '5832'
pubrep_id: '622'
quality_controlled: '1'
related_material:
record:
- id: '534'
relation: later_version
status: public
scopus_import: 1
status: public
title: Finding non-orientable surfaces in 3-manifolds
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 51
year: '2016'
...
---
_id: '1685'
abstract:
- lang: eng
text: "Given a graph G cellularly embedded on a surface Σ of genus g, a cut graph
is a subgraph of G such that cutting Σ along G yields a topological disk. We provide
a fixed parameter tractable approximation scheme for the problem of computing
the shortest cut graph, that is, for any ε > 0, we show how to compute a (1 + ε)
approximation of the shortest cut graph in time f(ε, g)n3.\r\nOur techniques first
rely on the computation of a spanner for the problem using the technique of brick
decompositions, to reduce the problem to the case of bounded tree-width. Then,
to solve the bounded tree-width case, we introduce a variant of the surface-cut
decomposition of Rué, Sau and Thilikos, which may be of independent interest."
alternative_title:
- LNCS
author:
- first_name: Vincent
full_name: Cohen Addad, Vincent
last_name: Cohen Addad
- first_name: Arnaud N
full_name: De Mesmay, Arnaud N
id: 3DB2F25C-F248-11E8-B48F-1D18A9856A87
last_name: De Mesmay
citation:
ama: 'Cohen Addad V, de Mesmay AN. A fixed parameter tractable approximation scheme
for the optimal cut graph of a surface. In: Vol 9294. Springer; 2015:386-398.
doi:10.1007/978-3-662-48350-3_33'
apa: 'Cohen Addad, V., & de Mesmay, A. N. (2015). A fixed parameter tractable
approximation scheme for the optimal cut graph of a surface (Vol. 9294, pp. 386–398).
Presented at the ESA: European Symposium on Algorithms, Patras, Greece: Springer.
https://doi.org/10.1007/978-3-662-48350-3_33'
chicago: Cohen Addad, Vincent, and Arnaud N de Mesmay. “A Fixed Parameter Tractable
Approximation Scheme for the Optimal Cut Graph of a Surface,” 9294:386–98. Springer,
2015. https://doi.org/10.1007/978-3-662-48350-3_33.
ieee: 'V. Cohen Addad and A. N. de Mesmay, “A fixed parameter tractable approximation
scheme for the optimal cut graph of a surface,” presented at the ESA: European
Symposium on Algorithms, Patras, Greece, 2015, vol. 9294, pp. 386–398.'
ista: 'Cohen Addad V, de Mesmay AN. 2015. A fixed parameter tractable approximation
scheme for the optimal cut graph of a surface. ESA: European Symposium on Algorithms,
LNCS, vol. 9294, 386–398.'
mla: Cohen Addad, Vincent, and Arnaud N. de Mesmay. A Fixed Parameter Tractable
Approximation Scheme for the Optimal Cut Graph of a Surface. Vol. 9294, Springer,
2015, pp. 386–98, doi:10.1007/978-3-662-48350-3_33.
short: V. Cohen Addad, A.N. de Mesmay, in:, Springer, 2015, pp. 386–398.
conference:
end_date: 2015-09-16
location: Patras, Greece
name: 'ESA: European Symposium on Algorithms'
start_date: 2015-09-14
date_created: 2018-12-11T11:53:27Z
date_published: 2015-09-01T00:00:00Z
date_updated: 2021-01-12T06:52:31Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/978-3-662-48350-3_33
ec_funded: 1
intvolume: ' 9294'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1507.01688
month: '09'
oa: 1
oa_version: Preprint
page: 386 - 398
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication_status: published
publisher: Springer
publist_id: '5462'
quality_controlled: '1'
scopus_import: 1
status: public
title: A fixed parameter tractable approximation scheme for the optimal cut graph
of a surface
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9294
year: '2015'
...
---
_id: '1730'
abstract:
- lang: eng
text: How much cutting is needed to simplify the topology of a surface? We provide
bounds for several instances of this question, for the minimum length of topologically
non-trivial closed curves, pants decompositions, and cut graphs with a given combinatorial
map in triangulated combinatorial surfaces (or their dual cross-metric counterpart).
Our work builds upon Riemannian systolic inequalities, which bound the minimum
length of non-trivial closed curves in terms of the genus and the area of the
surface. We first describe a systematic way to translate Riemannian systolic inequalities
to a discrete setting, and vice-versa. This implies a conjecture by Przytycka
and Przytycki (Graph structure theory. Contemporary Mathematics, vol. 147, 1993),
a number of new systolic inequalities in the discrete setting, and the fact that
a theorem of Hutchinson on the edge-width of triangulated surfaces and Gromov’s
systolic inequality for surfaces are essentially equivalent. We also discuss how
these proofs generalize to higher dimensions. Then we focus on topological decompositions
of surfaces. Relying on ideas of Buser, we prove the existence of pants decompositions
of length O(g^(3/2)n^(1/2)) for any triangulated combinatorial surface of genus
g with n triangles, and describe an O(gn)-time algorithm to compute such a decomposition.
Finally, we consider the problem of embedding a cut graph (or more generally a
cellular graph) with a given combinatorial map on a given surface. Using random
triangulations, we prove (essentially) that, for any choice of a combinatorial
map, there are some surfaces on which any cellular embedding with that combinatorial
map has length superlinear in the number of triangles of the triangulated combinatorial
surface. There is also a similar result for graphs embedded on polyhedral triangulations.
author:
- first_name: Éric
full_name: Colin De Verdière, Éric
last_name: Colin De Verdière
- first_name: Alfredo
full_name: Hubard, Alfredo
last_name: Hubard
- first_name: Arnaud N
full_name: De Mesmay, Arnaud N
id: 3DB2F25C-F248-11E8-B48F-1D18A9856A87
last_name: De Mesmay
citation:
ama: Colin De Verdière É, Hubard A, de Mesmay AN. Discrete systolic inequalities
and decompositions of triangulated surfaces. Discrete & Computational Geometry.
2015;53(3):587-620. doi:10.1007/s00454-015-9679-9
apa: Colin De Verdière, É., Hubard, A., & de Mesmay, A. N. (2015). Discrete
systolic inequalities and decompositions of triangulated surfaces. Discrete
& Computational Geometry. Springer. https://doi.org/10.1007/s00454-015-9679-9
chicago: Colin De Verdière, Éric, Alfredo Hubard, and Arnaud N de Mesmay. “Discrete
Systolic Inequalities and Decompositions of Triangulated Surfaces.” Discrete
& Computational Geometry. Springer, 2015. https://doi.org/10.1007/s00454-015-9679-9.
ieee: É. Colin De Verdière, A. Hubard, and A. N. de Mesmay, “Discrete systolic inequalities
and decompositions of triangulated surfaces,” Discrete & Computational
Geometry, vol. 53, no. 3. Springer, pp. 587–620, 2015.
ista: Colin De Verdière É, Hubard A, de Mesmay AN. 2015. Discrete systolic inequalities
and decompositions of triangulated surfaces. Discrete & Computational Geometry.
53(3), 587–620.
mla: Colin De Verdière, Éric, et al. “Discrete Systolic Inequalities and Decompositions
of Triangulated Surfaces.” Discrete & Computational Geometry, vol.
53, no. 3, Springer, 2015, pp. 587–620, doi:10.1007/s00454-015-9679-9.
short: É. Colin De Verdière, A. Hubard, A.N. de Mesmay, Discrete & Computational
Geometry 53 (2015) 587–620.
date_created: 2018-12-11T11:53:42Z
date_published: 2015-04-02T00:00:00Z
date_updated: 2021-01-12T06:52:49Z
day: '02'
department:
- _id: UlWa
doi: 10.1007/s00454-015-9679-9
intvolume: ' 53'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1408.4036
month: '04'
oa: 1
oa_version: Preprint
page: 587 - 620
publication: Discrete & Computational Geometry
publication_status: published
publisher: Springer
publist_id: '5397'
quality_controlled: '1'
scopus_import: 1
status: public
title: Discrete systolic inequalities and decompositions of triangulated surfaces
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 53
year: '2015'
...