On the treewidth of triangulated 3-manifolds

DOI10.20382/JOGC.V10I2A5zbMATH Open1504.57025arXiv1712.00434MaRDI QIDQ5207873FDOQ5207873

Authors: Kristóf Huszár, Jonathan Spreer, Uli Wagner 

Publication date: 13 January 2020

Abstract: In graph theory, as well as in 3-manifold topology, there exist several width-type parameters to describe how "simple" or "thin" a given graph or 3-manifold is. These parameters, such as pathwidth or treewidth for graphs, or the concept of thin position for 3-manifolds, play an important role when studying algorithmic problems; in particular, there is a variety of problems in computational 3-manifold 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 3-manifold admits a triangulation of bounded treewidth. We show that this is not the case, i.e., that there exists an infinite family of closed 3-manifolds 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, of Scharlemann and Thompson, and of Scharlemann, Schultens and Saito by exhibiting explicit connections between the topology of a 3-manifold M on the one hand and width-type 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 3-manifold topology. In particular, we show that if a closed, orientable, irreducible, non-Haken 3-manifold M has a triangulation of treewidth (resp. pathwidth) k then the Heegaard genus of M is at most 18(k+1) (resp. 4(3k+1)).

Full work available at URL: https://arxiv.org/abs/1712.00434

Recommendations

• scientific article; zbMATH DE number 7236450
• On the pathwidth of hyperbolic 3-manifolds
• FACE PAIRING GRAPHS AND 3-MANIFOLD ENUMERATION
• Treewidth, crushing and hyperbolic volume
• scientific article; zbMATH DE number 1021707

zbMATH Keywords

bounded treewidth3-manifolddual graph

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Relations of low-dimensional topology with graph theory (57M15) Triangulating manifolds (57Q15) General topology of 3-manifolds (57K30)

Cited In (7)

• A polynomial-time algorithm to compute Turaev-Viro invariants \(\mathrm{TV}_{4,q}\) of 3-manifolds with bounded first Betti number
• Treewidth, crushing and hyperbolic volume
• Title not available (Why is that?)
• On the cut number of a \(3\)-manifold
• The average edge order of triangulations of 3-manifolds with boundary
• On the pathwidth of hyperbolic 3-manifolds
• On the rooted forests in triangulated closed manifolds

This page was built for publication: On the treewidth of triangulated 3-manifolds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207873)