Abstract
In graph theory, as well as in 3manifold topology, there exist several widthtype parameters to describe how "simple" or "thin" a given graph or 3manifold is. These parameters, such as pathwidth or treewidth for graphs, or the concept of thin position for 3manifolds, play an important role when studying algorithmic problems; in particular, there is a variety of problems in computational 3manifold 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 3manifold admits a triangulation of bounded treewidth. We show that this is not the case, i.e., that there exists an infinite family of closed 3manifolds 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 3manifold M on the one hand and widthtype 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 3manifold topology. In particular, we show that if a closed, orientable, irreducible, nonHaken 3manifold 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)).
BibTeX  Entry
@InProceedings{huszr_et_al:LIPIcs:2018:8759,
author = {Krist{\'o}f Husz{\'a}r and Jonathan Spreer and Uli Wagner},
title = {{On the Treewidth of Triangulated 3Manifolds}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {46:146:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770668},
ISSN = {18688969},
year = {2018},
volume = {99},
editor = {Bettina Speckmann and Csaba D. T{\'o}th},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8759},
URN = {urn:nbn:de:0030drops87591},
doi = {10.4230/LIPIcs.SoCG.2018.46},
annote = {Keywords: computational topology, triangulations of 3manifolds, thin position, fixedparameter tractability, congestion, treewidth}
}
Keywords: 

computational topology, triangulations of 3manifolds, thin position, fixedparameter tractability, congestion, treewidth 
Seminar: 

34th International Symposium on Computational Geometry (SoCG 2018) 
Issue Date: 

2018 
Date of publication: 

24.05.2018 