On the Treewidth of Triangulated 3-Manifolds

K. Huszár, J. Spreer, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 46.

Download
OA 642.52 KB

Conference Paper | Published | English
Department
Series Title
LIPIcs
Abstract
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)).
Publishing Year
Date Published
2018-06-01
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).
Volume
99
Article Number
46
Conference
SoCG: Symposium on Computational Geometry
Conference Location
Budapest, Hungary
Conference Date
2018-06-11 – 2018-06-14
ISSN
IST-REx-ID

Cite this

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:46. doi:10.4230/LIPIcs.SoCG.2018.46
Huszár, K., Spreer, J., & Wagner, U. (2018). On the Treewidth of Triangulated 3-Manifolds (Vol. 99, p. 46). 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
Huszár, Kristóf, Jonathan Spreer, and Uli Wagner. “On the Treewidth of Triangulated 3-Manifolds,” 99:46. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPIcs.SoCG.2018.46.
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, p. 46.
Huszár K, Spreer J, Wagner U. 2018. On the Treewidth of Triangulated 3-Manifolds. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 99. 46.
Huszár, Kristóf, et al. On the Treewidth of Triangulated 3-Manifolds. Vol. 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 46, doi:10.4230/LIPIcs.SoCG.2018.46.
All files available under the following license(s):
Creative Commons License:
CC-BYCreative Commons Attribution 4.0 International Public License (CC-BY 4.0)
Main File(s)
File Name
Access Level
OA Open Access
Last Uploaded
2018-12-17T15:32:38Z


Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1712.00434

Search this title in

Google Scholar