---
_id: '8032'
abstract:
- lang: eng
text: "Algorithms in computational 3-manifold topology typically take a triangulation
as an input and return topological information about the underlying 3-manifold.
However, extracting the desired information from a triangulation (e.g., evaluating
an invariant) is often computationally very expensive. In recent years this complexity
barrier has been successfully tackled in some cases by importing ideas from the
theory of parameterized algorithms into the realm of 3-manifolds. Various computationally
hard problems were shown to be efficiently solvable for input triangulations that
are sufficiently “tree-like.”\r\nIn this thesis we focus on the key combinatorial
parameter in the above context: we consider the treewidth of a compact, orientable
3-manifold, i.e., the smallest treewidth of the dual graph of any triangulation
thereof. By building on the work of Scharlemann–Thompson and Scharlemann–Schultens–Saito
on generalized Heegaard splittings, and on the work of Jaco–Rubinstein on layered
triangulations, we establish quantitative relations between the treewidth and
classical topological invariants of a 3-manifold. In particular, among other results,
we show that the treewidth of a closed, orientable, irreducible, non-Haken 3-manifold
is always within a constant factor of its Heegaard genus."
acknowledged_ssus:
- _id: E-Lib
- _id: CampIT
alternative_title:
- ISTA Thesis
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
citation:
ama: Huszár K. Combinatorial width parameters for 3-dimensional manifolds. 2020.
doi:10.15479/AT:ISTA:8032
apa: Huszár, K. (2020). Combinatorial width parameters for 3-dimensional manifolds.
Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:8032
chicago: Huszár, Kristóf. “Combinatorial Width Parameters for 3-Dimensional Manifolds.”
Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:8032.
ieee: K. Huszár, “Combinatorial width parameters for 3-dimensional manifolds,” Institute
of Science and Technology Austria, 2020.
ista: Huszár K. 2020. Combinatorial width parameters for 3-dimensional manifolds.
Institute of Science and Technology Austria.
mla: Huszár, Kristóf. Combinatorial Width Parameters for 3-Dimensional Manifolds.
Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:8032.
short: K. Huszár, Combinatorial Width Parameters for 3-Dimensional Manifolds, Institute
of Science and Technology Austria, 2020.
date_created: 2020-06-26T10:00:36Z
date_published: 2020-06-26T00:00:00Z
date_updated: 2023-09-07T13:18:27Z
day: '26'
ddc:
- '514'
degree_awarded: PhD
department:
- _id: UlWa
doi: 10.15479/AT:ISTA:8032
file:
- access_level: open_access
checksum: bd8be6e4f1addc863dfcc0fad29ee9c3
content_type: application/pdf
creator: khuszar
date_created: 2020-06-26T10:03:58Z
date_updated: 2020-07-14T12:48:08Z
file_id: '8034'
file_name: Kristof_Huszar-Thesis.pdf
file_size: 2637562
relation: main_file
- access_level: closed
checksum: d5f8456202b32f4a77552ef47a2837d1
content_type: application/x-zip-compressed
creator: khuszar
date_created: 2020-06-26T10:10:06Z
date_updated: 2020-07-14T12:48:08Z
file_id: '8035'
file_name: Kristof_Huszar-Thesis-source.zip
file_size: 7163491
relation: source_file
file_date_updated: 2020-07-14T12:48:08Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: xviii+120
publication_identifier:
isbn:
- 978-3-99078-006-0
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '6556'
relation: dissertation_contains
status: public
- id: '7093'
relation: dissertation_contains
status: public
status: public
supervisor:
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
- first_name: Jonathan
full_name: Spreer, Jonathan
last_name: Spreer
title: Combinatorial width parameters for 3-dimensional 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: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2020'
...
---
_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: '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
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
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
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'
...
---
_id: '285'
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. In 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). We derive
these results from work of Agol and of Scharlemann and Thompson, 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 48(k+1) (resp. 4(3k+1)).
acknowledgement: Research of the second author was supported by the Einstein Foundation
(project “Einstein Visiting Fellow Santos”) and by the Simons Foundation (“Simons
Visiting Professors” program).
alternative_title:
- LIPIcs
article_number: '46'
article_processing_charge: No
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.
In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPIcs.SoCG.2018.46'
apa: 'Huszár, K., Spreer, J., & Wagner, U. (2018). On the treewidth of triangulated
3-manifolds (Vol. 99). Presented at the SoCG: Symposium on Computational Geometry,
Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2018.46'
chicago: Huszár, Kristóf, Jonathan Spreer, and Uli Wagner. “On the Treewidth of
Triangulated 3-Manifolds,” Vol. 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2018. https://doi.org/10.4230/LIPIcs.SoCG.2018.46.
ieee: 'K. Huszár, J. Spreer, and U. Wagner, “On the treewidth of triangulated 3-manifolds,”
presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary,
2018, vol. 99.'
ista: 'Huszár K, Spreer J, Wagner U. 2018. On the treewidth of triangulated 3-manifolds.
SoCG: Symposium on Computational Geometry, LIPIcs, vol. 99, 46.'
mla: Huszár, Kristóf, et al. On the Treewidth of Triangulated 3-Manifolds.
Vol. 99, 46, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:10.4230/LIPIcs.SoCG.2018.46.
short: K. Huszár, J. Spreer, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2018.
conference:
end_date: 2018-06-14
location: Budapest, Hungary
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2018-06-11
date_created: 2018-12-11T11:45:37Z
date_published: 2018-06-01T00:00:00Z
date_updated: 2023-09-06T11:13:41Z
day: '01'
ddc:
- '516'
- '000'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2018.46
external_id:
arxiv:
- '1712.00434'
file:
- access_level: open_access
checksum: 530d084116778135d5bffaa317479cac
content_type: application/pdf
creator: dernst
date_created: 2018-12-17T15:32:38Z
date_updated: 2020-07-14T12:45:51Z
file_id: '5713'
file_name: 2018_LIPIcs_Huszar.pdf
file_size: 642522
relation: main_file
file_date_updated: 2020-07-14T12:45:51Z
has_accepted_license: '1'
intvolume: ' 99'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Submitted Version
publication_identifier:
issn:
- '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '7614'
quality_controlled: '1'
related_material:
record:
- id: '7093'
relation: later_version
status: public
scopus_import: 1
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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 99
year: '2018'
...
---
_id: '7038'
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: Michal
full_name: Rolinek, Michal
id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
last_name: Rolinek
citation:
ama: Huszár K, Rolinek M. Playful Math - An Introduction to Mathematical Games.
IST Austria
apa: Huszár, K., & Rolinek, M. (n.d.). Playful Math - An introduction to
mathematical games. IST Austria.
chicago: Huszár, Kristóf, and Michal Rolinek. Playful Math - An Introduction
to Mathematical Games. IST Austria, n.d.
ieee: K. Huszár and M. Rolinek, Playful Math - An introduction to mathematical
games. IST Austria.
ista: Huszár K, Rolinek M. Playful Math - An introduction to mathematical games,
IST Austria, 5p.
mla: Huszár, Kristóf, and Michal Rolinek. Playful Math - An Introduction to Mathematical
Games. IST Austria.
short: K. Huszár, M. Rolinek, Playful Math - An Introduction to Mathematical Games,
IST Austria, n.d.
date_created: 2019-11-18T15:57:05Z
date_published: 2014-06-30T00:00:00Z
date_updated: 2020-07-14T23:11:45Z
day: '30'
ddc:
- '510'
department:
- _id: VlKo
- _id: UlWa
file:
- access_level: open_access
checksum: 2b94e5e1f4c3fe8ab89b12806276fb09
content_type: application/pdf
creator: dernst
date_created: 2019-11-18T15:57:51Z
date_updated: 2020-07-14T12:47:48Z
file_id: '7039'
file_name: 2014_Playful_Math_Huszar.pdf
file_size: 511233
relation: main_file
file_date_updated: 2020-07-14T12:47:48Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: '5'
publication_status: draft
publisher: IST Austria
status: public
title: Playful Math - An introduction to mathematical games
type: working_paper
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...