3-manifolds are commonly represented as triangulations, consisting of abstract tetrahedra whose triangular faces are identified in pairs. The combinatorial sparsity of a triangulation, as measured by the treewidth of its dual graph, plays a fundamental role in the design of parameterized algorithms. In this work, we investigate algorithmic procedures that transform or modify a given triangulation while controlling specific sparsity parameters. First, we revisit a standard, linear-time algorithm that converts a given triangulation into a Heegaard diagram of the underlying 3-manifold, showing that the construction preserves treewidth. We apply this construction to exhibit a fixed-parameter tractable framework for computing Kuperberg's quantum invariants of 3-manifolds. Second, we present a quasi-linear-time algorithm that retriangulates a given triangulation into one with maximum edge valence of at most nine, while only moderately increasing the treewidth of the dual graph. Combining these two algorithms yields a quasi-linear-time algorithm that produces, from a given triangulation, a Heegaard diagram in which every attaching curve intersects at most nine others.

Building on Whitney's classical method of triangulating smooth manifolds, we show that every compact $d$-dimensional smooth manifold admits a triangulation with dual graph of twin-width at most $d^{O(d)}$. In particular, it follows that every compact 3-manifold has a triangulation with dual graph of bounded twin-width. This is in sharp contrast to the case of treewidth, where for any natural number $n$ there exists a closed 3-manifold such that every triangulation thereof has dual graph with treewidth at least $n$. To establish this result, we bound the twin-width of the incidence graph of the $d$-skeleton of the second barycentric subdivision of the $2d$-dimensional hypercubic honeycomb. We also show that every compact, piecewise-linear (hence smooth) $d$-dimensional manifold has triangulations where the dual graph has an arbitrarily large twin-width.

Abstract Motivated by the algorithmic study of 3-dimensional manifolds, we explore the structural relationship between the JSJ decomposition of a given 3-manifold and its triangulations. Building on work of Bachman, Derby-Talbot and Sedgwick, we show that a “sufficiently complicated” JSJ decomposition of a 3-manifold enforces a “complicated structure” for all of its triangulations. More concretely, we show that, under certain conditions, the treewidth (resp. pathwidth) of the graph that captures the incidences between the pieces of the JSJ decomposition of an irreducible, closed, orientable 3-manifold $$\mathscr {M}$$ M yields a linear lower bound on its treewidth $$\operatorname {tw} (\mathscr {M})$$ tw ( M ) (resp. pathwidth $$\operatorname {pw} (\mathscr {M})$$ pw ( M ) ), defined as the smallest treewidth (resp. pathwidth) of the dual graph of any triangulation of $$\mathscr {M}$$ M . We present several applications of this result. We give the first example of an infinite family of bounded-treewidth 3-manifolds with unbounded pathwidth. We construct Haken 3-manifolds with arbitrarily large treewidth—previously the existence of such 3-manifolds was only known in the non-Haken case. We also show that the problem of providing a constant-factor approximation for the treewidth (resp. pathwidth) of bounded-degree graphs efficiently reduces to computing a constant-factor approximation for the treewidth (resp. pathwidth) of 3-manifolds.

Full version of the conference paper. 22 pages, 19 figures

Motivated by fixed-parameter tractable (FPT) problems in computational topology, we consider the treewidth of a compact, connected 3-manifold $M$ defined by \[ \operatorname{tw}(M) = \min\{\operatorname{tw}(\Gamma(\mathcal{T})):\mathcal{T}~\text{is a triangulation of }M\}, \] where $\Gamma(\mathcal{T})$ denotes the dual graph of $\mathcal{T}$. In this setting the relationship between the topology of a 3-manifold and its treewidth is of particular interest. First, as a corollary of work of Jaco and Rubinstein, we prove that for any closed, orientable 3-manifold $M$ the treewidth $\operatorname{tw}(M)$ is at most $4\mathfrak{g}(M)-2$ where $\mathfrak{g}(M)$ denotes the Heegaard genus of $M$. In combination with our earlier work with Wagner, this yields that for non-Haken manifolds the Heegaard genus and the treewidth are within a constant factor. Second, we characterize all 3-manifolds of treewidth one: These are precisely the lens spaces and a single other Seifert fibered space. Furthermore, we show that all remaining orientable Seifert fibered spaces over the 2-sphere or a non-orientable surface have treewidth two. In particular, for every spherical 3-manifold we exhibit a triangulation of treewidth at most two. Our results further validate the parameter of treewidth (and other related parameters such as cutwidth, or congestion) to be useful for topological computing, and also shed more light on the scope of existing FPT algorithms in the field.