Combinatorial width parameters for 3-dimensional manifolds
Huszar, Kristof
Combinatorial width parameters for 3-dimensional manifolds - IST Austria 2020
Thesis
Abstract Acknowledgments About the Author List of Publications List of Tables List of Figures 1 Introduction 2 Preliminaries on Graphs and Parameterized Complexity 3 A Primer on 3-Manifolds 4 Interfaces between Combinatorics and Topology 5 From Combinatorics to Topology and Back – In a Quantitative Way 6 The Classification of 3-Manifolds with Treewidth One 7 Some 3-Manifolds with Treewidth Two Appendix A Computational Aspects Appendix B High-Treewidth Triangulations Appendix C The 1-Tetrahedron Layered Solid Torus Appendix D An Algorithmic Aspect of Layered Triangulations Appendix E Generating Treewidth Two Triangulations Using Regina Bibliography
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.
Combinatorial width parameters for 3-dimensional manifolds - IST Austria 2020
Thesis
Abstract Acknowledgments About the Author List of Publications List of Tables List of Figures 1 Introduction 2 Preliminaries on Graphs and Parameterized Complexity 3 A Primer on 3-Manifolds 4 Interfaces between Combinatorics and Topology 5 From Combinatorics to Topology and Back – In a Quantitative Way 6 The Classification of 3-Manifolds with Treewidth One 7 Some 3-Manifolds with Treewidth Two Appendix A Computational Aspects Appendix B High-Treewidth Triangulations Appendix C The 1-Tetrahedron Layered Solid Torus Appendix D An Algorithmic Aspect of Layered Triangulations Appendix E Generating Treewidth Two Triangulations Using Regina Bibliography
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.