Combinatorial width parameters for 3-dimensional manifolds

By: Material type: TextTextPublication details: IST Austria 2020Online resources:
Contents:
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
Summary: 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.
List(s) this item appears in: ISTA Thesis
Holdings
Item type Current library Call number Status Date due Barcode Item holds
Book Book Library Quiet Room (Browse shelf(Opens below)) Available AT-ISTA#002162
Total holds: 0

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.

Powered by Koha