---
_id: '7093'
abstract:
- lang: eng
text: "In graph theory, as well as in 3-manifold topology, there exist several width-type
parameters to describe how \"simple\" or \"thin\" a given graph or 3-manifold
is. These parameters, such as pathwidth or treewidth for graphs, or the concept
of thin position for 3-manifolds, play an important role when studying algorithmic
problems; in particular, there is a variety of problems in computational 3-manifold
topology - some of them known to be computationally hard in general - that become
solvable in polynomial time as soon as the dual graph of the input triangulation
has bounded treewidth.\r\nIn view of these algorithmic results, it is natural
to ask whether every 3-manifold admits a triangulation of bounded treewidth. We
show that this is not the case, i.e., that there exists an infinite family of
closed 3-manifolds not admitting triangulations of bounded pathwidth or treewidth
(the latter implies the former, but we present two separate proofs).\r\nWe derive
these results from work of Agol, of Scharlemann and Thompson, and of Scharlemann,
Schultens and Saito by exhibiting explicit connections between the topology of
a 3-manifold M on the one hand and width-type parameters of the dual graphs of
triangulations of M on the other hand, answering a question that had been raised
repeatedly by researchers in computational 3-manifold topology. In particular,
we show that if a closed, orientable, irreducible, non-Haken 3-manifold M has
a triangulation of treewidth (resp. pathwidth) k then the Heegaard genus of M
is at most 18(k+1) (resp. 4(3k+1))."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Kristóf
full_name: Huszár, Kristóf
id: 33C26278-F248-11E8-B48F-1D18A9856A87
last_name: Huszár
orcid: 0000-0002-5445-5057
- first_name: Jonathan
full_name: Spreer, Jonathan
last_name: Spreer
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Huszár K, Spreer J, Wagner U. On the treewidth of triangulated 3-manifolds.
Journal of Computational Geometry. 2019;10(2):70–98. doi:10.20382/JOGC.V10I2A5
apa: Huszár, K., Spreer, J., & Wagner, U. (2019). On the treewidth of triangulated
3-manifolds. Journal of Computational Geometry. Computational Geometry
Laborartoy. https://doi.org/10.20382/JOGC.V10I2A5
chicago: Huszár, Kristóf, Jonathan Spreer, and Uli Wagner. “On the Treewidth of
Triangulated 3-Manifolds.” Journal of Computational Geometry. Computational
Geometry Laborartoy, 2019. https://doi.org/10.20382/JOGC.V10I2A5.
ieee: K. Huszár, J. Spreer, and U. Wagner, “On the treewidth of triangulated 3-manifolds,”
Journal of Computational Geometry, vol. 10, no. 2. Computational Geometry
Laborartoy, pp. 70–98, 2019.
ista: Huszár K, Spreer J, Wagner U. 2019. On the treewidth of triangulated 3-manifolds.
Journal of Computational Geometry. 10(2), 70–98.
mla: Huszár, Kristóf, et al. “On the Treewidth of Triangulated 3-Manifolds.” Journal
of Computational Geometry, vol. 10, no. 2, Computational Geometry Laborartoy,
2019, pp. 70–98, doi:10.20382/JOGC.V10I2A5.
short: K. Huszár, J. Spreer, U. Wagner, Journal of Computational Geometry 10 (2019)
70–98.
date_created: 2019-11-23T12:14:09Z
date_published: 2019-11-01T00:00:00Z
date_updated: 2023-09-07T13:18:26Z
day: '01'
ddc:
- '514'
department:
- _id: UlWa
doi: 10.20382/JOGC.V10I2A5
external_id:
arxiv:
- '1712.00434'
file:
- access_level: open_access
checksum: c872d590d38d538404782bca20c4c3f5
content_type: application/pdf
creator: khuszar
date_created: 2019-11-23T12:35:16Z
date_updated: 2020-07-14T12:47:49Z
file_id: '7094'
file_name: 479-1917-1-PB.pdf
file_size: 857590
relation: main_file
file_date_updated: 2020-07-14T12:47:49Z
has_accepted_license: '1'
intvolume: ' 10'
issue: '2'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
page: 70–98
publication: Journal of Computational Geometry
publication_identifier:
issn:
- 1920-180X
publication_status: published
publisher: Computational Geometry Laborartoy
quality_controlled: '1'
related_material:
record:
- id: '285'
relation: earlier_version
status: public
- id: '8032'
relation: part_of_dissertation
status: public
status: public
title: On the treewidth of triangulated 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: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 10
year: '2019'
...
---
_id: '6515'
abstract:
- lang: eng
text: We give non-degeneracy criteria for Riemannian simplices based on simplices
in spaces of constant sectional curvature. It extends previous work on Riemannian
simplices, where we developed Riemannian simplices with respect to Euclidean reference
simplices. The criteria we give in this article are in terms of quality measures
for spaces of constant curvature that we develop here. We see that simplices in
spaces that have nearly constant curvature, are already non-degenerate under very
weak quality demands. This is of importance because it allows for sampling of
Riemannian manifolds based on anisotropy of the manifold and not (absolute) curvature.
author:
- first_name: Ramsay
full_name: Dyer, Ramsay
last_name: Dyer
- first_name: Gert
full_name: Vegter, Gert
last_name: Vegter
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: Dyer R, Vegter G, Wintraecken M. Simplices modelled on spaces of constant curvature.
Journal of Computational Geometry . 2019;10(1):223–256. doi:10.20382/jocg.v10i1a9
apa: Dyer, R., Vegter, G., & Wintraecken, M. (2019). Simplices modelled on spaces
of constant curvature. Journal of Computational Geometry . Carleton University.
https://doi.org/10.20382/jocg.v10i1a9
chicago: Dyer, Ramsay, Gert Vegter, and Mathijs Wintraecken. “Simplices Modelled
on Spaces of Constant Curvature.” Journal of Computational Geometry . Carleton
University, 2019. https://doi.org/10.20382/jocg.v10i1a9.
ieee: R. Dyer, G. Vegter, and M. Wintraecken, “Simplices modelled on spaces of constant
curvature,” Journal of Computational Geometry , vol. 10, no. 1. Carleton
University, pp. 223–256, 2019.
ista: Dyer R, Vegter G, Wintraecken M. 2019. Simplices modelled on spaces of constant
curvature. Journal of Computational Geometry . 10(1), 223–256.
mla: Dyer, Ramsay, et al. “Simplices Modelled on Spaces of Constant Curvature.”
Journal of Computational Geometry , vol. 10, no. 1, Carleton University,
2019, pp. 223–256, doi:10.20382/jocg.v10i1a9.
short: R. Dyer, G. Vegter, M. Wintraecken, Journal of Computational Geometry 10
(2019) 223–256.
date_created: 2019-06-03T09:35:33Z
date_published: 2019-07-01T00:00:00Z
date_updated: 2021-01-12T08:07:50Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.20382/jocg.v10i1a9
ec_funded: 1
file:
- access_level: open_access
checksum: 57b4df2f16a74eb499734ec8ee240178
content_type: application/pdf
creator: mwintrae
date_created: 2019-06-03T09:30:01Z
date_updated: 2020-07-14T12:47:32Z
file_id: '6516'
file_name: mainJournalFinal.pdf
file_size: 2170882
relation: main_file
file_date_updated: 2020-07-14T12:47:32Z
has_accepted_license: '1'
intvolume: ' 10'
issue: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 223–256
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 'Journal of Computational Geometry '
publication_identifier:
issn:
- 1920-180X
publication_status: published
publisher: Carleton University
quality_controlled: '1'
scopus_import: 1
status: public
title: Simplices modelled on spaces of constant curvature
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: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 10
year: '2019'
...