Combinatorial width parameters for 3-dimensional manifolds

Huszár K. 2020. Combinatorial width parameters for 3-dimensional manifolds. Institute of Science and Technology Austria.

Download
OA Kristof_Huszar-Thesis.pdf 2.64 MB [Published Version]

Thesis | PhD | Published | English
Supervisor
Wagner, UliISTA ; Spreer, Jonathan
Department
Series Title
ISTA Thesis
Abstract
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.” In 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.
Publishing Year
Date Published
2020-06-26
Publisher
Institute of Science and Technology Austria
Acknowledged SSUs
Page
xviii+120
ISSN
IST-REx-ID

Cite this

Huszár K. Combinatorial width parameters for 3-dimensional manifolds. 2020. doi:10.15479/AT:ISTA:8032
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
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.
K. Huszár, “Combinatorial width parameters for 3-dimensional manifolds,” Institute of Science and Technology Austria, 2020.
Huszár K. 2020. Combinatorial width parameters for 3-dimensional manifolds. Institute of Science and Technology Austria.
Huszár, Kristóf. Combinatorial Width Parameters for 3-Dimensional Manifolds. Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:8032.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
Access Level
OA Open Access
Date Uploaded
2020-06-26
MD5 Checksum
bd8be6e4f1addc863dfcc0fad29ee9c3

Source File
Access Level
Restricted Closed Access
Date Uploaded
2020-06-26
MD5 Checksum
d5f8456202b32f4a77552ef47a2837d1

Material in ISTA:
Dissertation containing ISTA record
Dissertation containing ISTA record

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar
ISBN Search