---
_id: '6556'
abstract:
- lang: eng
text: 'Motivated by fixed-parameter tractable (FPT) problems in computational topology,
we consider the treewidth tw(M) of a compact, connected 3-manifold M, defined
to be the minimum treewidth of the face pairing graph of any triangulation T of
M. In this setting the relationship between the topology of a 3-manifold and its
treewidth is of particular interest. First, as a corollary of work of Jaco and
Rubinstein, we prove that for any closed, orientable 3-manifold M the treewidth
tw(M) is at most 4g(M)-2, where g(M) denotes Heegaard genus of M. In combination
with our earlier work with Wagner, this yields that for non-Haken manifolds the
Heegaard genus and the treewidth are within a constant factor. Second, we characterize
all 3-manifolds of treewidth one: These are precisely the lens spaces and a single
other Seifert fibered space. Furthermore, we show that all remaining orientable
Seifert fibered spaces over the 2-sphere or a non-orientable surface have treewidth
two. In particular, for every spherical 3-manifold we exhibit a triangulation
of treewidth at most two. Our results further validate the parameter of treewidth
(and other related parameters such as cutwidth or congestion) to be useful for
topological computing, and also shed more light on the scope of existing FPT-algorithms
in the field.'
alternative_title:
- LIPIcs
article_processing_charge: No
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
citation:
ama: 'Huszár K, Spreer J. 3-manifold triangulations with small treewidth. In: 35th
International Symposium on Computational Geometry. Vol 129. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2019:44:1-44:20. doi:10.4230/LIPIcs.SoCG.2019.44'
apa: 'Huszár, K., & Spreer, J. (2019). 3-manifold triangulations with small
treewidth. In 35th International Symposium on Computational Geometry (Vol.
129, p. 44:1-44:20). Portland, Oregon, United States: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2019.44'
chicago: Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small
Treewidth.” In 35th International Symposium on Computational Geometry,
129:44:1-44:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPIcs.SoCG.2019.44.
ieee: K. Huszár and J. Spreer, “3-manifold triangulations with small treewidth,”
in 35th International Symposium on Computational Geometry, Portland, Oregon,
United States, 2019, vol. 129, p. 44:1-44:20.
ista: 'Huszár K, Spreer J. 2019. 3-manifold triangulations with small treewidth.
35th International Symposium on Computational Geometry. SoCG: Symposium on Computational
Geometry, LIPIcs, vol. 129, 44:1-44:20.'
mla: Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small
Treewidth.” 35th International Symposium on Computational Geometry, vol.
129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20, doi:10.4230/LIPIcs.SoCG.2019.44.
short: K. Huszár, J. Spreer, in:, 35th International Symposium on Computational
Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20.
conference:
end_date: 2019-06-21
location: Portland, Oregon, United States
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2019-06-18
date_created: 2019-06-11T20:09:57Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2023-09-07T13:18:26Z
day: '01'
ddc:
- '516'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2019.44
external_id:
arxiv:
- '1812.05528'
file:
- access_level: open_access
checksum: 29d18c435368468aa85823dabb157e43
content_type: application/pdf
creator: kschuh
date_created: 2019-06-12T06:45:33Z
date_updated: 2020-07-14T12:47:33Z
file_id: '6557'
file_name: 2019_LIPIcs-Huszar.pdf
file_size: 905885
relation: main_file
file_date_updated: 2020-07-14T12:47:33Z
has_accepted_license: '1'
intvolume: ' 129'
keyword:
- computational 3-manifold topology
- fixed-parameter tractability
- layered triangulations
- structural graph theory
- treewidth
- cutwidth
- Heegaard genus
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '06'
oa: 1
oa_version: Published Version
page: 44:1-44:20
publication: 35th International Symposium on Computational Geometry
publication_identifier:
isbn:
- 978-3-95977-104-7
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '8032'
relation: part_of_dissertation
status: public
scopus_import: '1'
status: public
title: 3-manifold triangulations with small treewidth
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 129
year: '2019'
...