On the treewidth of triangulated 3-manifolds
Huszár K, Spreer J, Wagner U. 2019. On the treewidth of triangulated 3-manifolds. Journal of Computational Geometry. 10(2), 70–98.
Download
Journal Article
| Published
| English
Author
Department
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, 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)).
Publishing Year
Date Published
2019-11-01
Journal Title
Journal of Computational Geometry
Volume
10
Issue
2
Page
70–98
ISSN
IST-REx-ID
Cite this
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
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
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.
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.
Huszár K, Spreer J, Wagner U. 2019. On the treewidth of triangulated 3-manifolds. Journal of Computational Geometry. 10(2), 70–98.
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.
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
479-1917-1-PB.pdf
857.59 KB
Access Level
Open Access
Date Uploaded
2019-11-23
MD5 Checksum
c872d590d38d538404782bca20c4c3f5
Material in ISTA:
Earlier Version
Part of this Dissertation
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 1712.00434