3-manifold triangulations with small treewidth

K. Huszár, J. Spreer, in:, 35th International Symposium on Computational Geometry (SoCG 2019), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019, p. 44:1-44:20.

Download
OA 905.88 KB

Conference Paper | Published | English
Author
;
Department
Abstract
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.
Publishing Year
Date Published
2019-06-01
Proceedings Title
35th International Symposium on Computational Geometry (SoCG 2019)
Volume
129
Page
44:1-44:20
Conference
SoCG: Symposium on Computational Geometry
Conference Location
Portland, Oregon, United States
Conference Date
2019-06-18 – 2019-06-21
ISSN
IST-REx-ID

Cite this

Huszár K, Spreer J. 3-manifold triangulations with small treewidth. In: 35th International Symposium on Computational Geometry (SoCG 2019). Vol 129. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik; 2019:44:1-44:20. doi:10.4230/LIPIcs.SoCG.2019.44
Huszár, K., & Spreer, J. (2019). 3-manifold triangulations with small treewidth. In 35th International Symposium on Computational Geometry (SoCG 2019) (Vol. 129, p. 44:1-44:20). Portland, Oregon, United States: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2019.44
Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small Treewidth.” In 35th International Symposium on Computational Geometry (SoCG 2019), 129:44:1-44:20. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019. https://doi.org/10.4230/LIPIcs.SoCG.2019.44.
K. Huszár and J. Spreer, “3-manifold triangulations with small treewidth,” in 35th International Symposium on Computational Geometry (SoCG 2019), Portland, Oregon, United States, 2019, vol. 129, p. 44:1-44:20.
Huszár K, Spreer J. 2019. 3-manifold triangulations with small treewidth. 35th International Symposium on Computational Geometry (SoCG 2019). SoCG: Symposium on Computational GeometryLeibniz International Proceedings in Informatics (LIPIcs) vol. 129. 44:1-44:20.
Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small Treewidth.” 35th International Symposium on Computational Geometry (SoCG 2019), vol. 129, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019, p. 44:1-44:20, doi:10.4230/LIPIcs.SoCG.2019.44.
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
2019-06-12T06:45:33Z


Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1812.05528

Search this title in

Google Scholar
ISBN Search