Treewidth and metric complexity for hyperbolic 3-manifolds

Treewidth is an invariant of graphs which measures how close a graph is to being a tree. A number of algorithms that are exponential over all graphs are polynomial over graphs of bounded tree width. The treewidth of a 3-manifold is the minimal treewidth of the dual graph of any triangulation of the manifold. A number of 3-manifold invariants which are exponential in the number of tetrahedra are polynomial for manifolds of bounded treewidth, for example, the Turaev-Viro invariants. We show that for hyperbolic 3-manifolds, treewidth is linearly related to a metric complexity defined in terms of Morse functions to trees. In particular, this shows that there are 3-manifolds of arbitrarily large treewidth. This is joint work with Diane Hoffoss.