# On Sparse Representations of 3-Manifolds

Kristóf Huszár, Clément Maria

► To cite this version:

Kristóf Huszár, Clément Maria. On Sparse Representations of 3-Manifolds. 2025. hal-05405102

HAL Id: hal-05405102

https://hal.science/hal-05405102v1

Preprint submitted on 8 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On Sparse Representations of 3-Manifolds

Kristóf Huszár

<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

Institute of Geometry, Graz University of Technology, Austria

Clément Maria

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /></figure>

Inria d'Université Côte d'Azur, France

## Abstract

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 describe a 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.

**2012 ACM Subject Classification** Mathematics of computing → Geometric topology; Theory of computation → Fixed parameter tractability

**Keywords and phrases** computational 3-manifold topology, fixed-parameter tractability, Heegaard splittings and diagrams, triangulations, edge valence, treewidth, quantum invariants, tensor networks

**Funding** Clément Maria: Partially supported by the ANR project ANR-20-CE48-0007 (AlgoKnot).

## 1 Introduction

Structural properties of triangulations—which are commonly used to encode 3-manifolds both in theory and in practice—can dramatically affect the feasibility of computations. Over the past decade, several fixed-parameter tractable (FPT) algorithms have been developed that efficiently solve provably hard problems on 3-manifolds, provided they are represented by triangulations that are sufficiently “thin” [7, 9, 10, 11, 12].<fnref n="1" /> On input triangulations with bounded *treewidth*<fnref n="2" /> these algorithms run in time polynomial in the number of tetrahedra.<fnref n="3" />

Motivated by these algorithms, several recent papers have investigated the quantitative relationship between the treewidth (and other width parameters) of triangulations and the corresponding quantities in various related representations of 3-manifolds. It has been shown that 3-manifolds with small Heegaard genus [19, 24], as well as hyperbolic 3-manifolds with small volume [23, 35], admit triangulations with small treewidth. At the same time, for certain 3-manifolds, a large Heegaard genus or a “complicated” JSJ decomposition can entirely preclude the existence of triangulations with small treewidth [25, 26].<fnref n="4" />

In this work, we also focus on algorithmic transformations of 3-manifold triangulations with a view toward parameterized algorithms and sparsity. We provide two main contributions.

<footnote n="1">¹ See [6, 32, 33, 34] for related FPT algorithms in knot theory, and the survey [30] for a broader context.</footnote>

<footnote n="2">² Treewidth is a graph parameter that quantifies the similarity of a given graph to any tree. We define the treewidth of a triangulation $\mathcal{T}$ as the treewidth of its dual graph $\Gamma(\mathcal{T})$. See Section 2 for details.</footnote>

<footnote n="3">³ Many of these algorithms have also been implemented in the topology software *Regina* [7].</footnote>

<footnote n="4">⁴ See [14, 31] for related structural results about knots and links and their diagrams.</footnote>
## 2 On Sparse Representations of 3-Manifolds

First, we revisit and analyze a classical construction that turns a triangulation $\mathcal{T}$ of a closed 3-manifold $\mathcal{M}$ into a Heegaard splitting and show that it yields a Heegaard diagram of $\mathcal{M}$, whose size and treewidth are linearly bounded by those of $\mathcal{T}$. More concretely, we prove

**Theorem 1.** Let $\mathcal{T}$ be a triangulation of a closed, orientable 3-manifold $\mathcal{M}$ with $n$ tetrahedra and dual graph $\Gamma(\mathcal{T})$. Let $\mathcal{D} := \mathcal{D}(\mathcal{T})$ be the Heegaard diagram of $\mathcal{M}$ induced by $\mathcal{T}$. Then, for the number of vertices and for the treewidth$^5$ of $\mathcal{D}$ and $\Gamma(\mathcal{T})$ we have

$$|V(\mathcal{D})| = 6n \quad (1a) \quad \text{and} \quad \text{tw}(\mathcal{D}) \le 12\text{tw}(\Gamma(\mathcal{T})) + 11. \quad (1b)$$

Moreover, given $\mathcal{T}$, the induced Heegaard diagram $\mathcal{D}$ can be constructed in $O(n)$ time.

Guided by this result, in Section 5 we investigate the complexity of computing Kuperberg's quantum invariants of oriented 3-manifolds [28], which are obtained from a Heegaard diagram by evaluating an associated tensor network. First, we show that this construction is width-preserving (Lemma 18). This insight, combined with Theorem 1 and results on the complexity of evaluating tensor networks [37, 40] (cf. Theorem 19), provides a framework for computing Kuperberg's invariants from triangulations that is FPT in the treewidth (Theorem 15).

**Remark.** The converse of Theorem 1, i.e., building a triangulation from a given Heegaard splitting in a width-preserving way, has been studied in [24] and, very recently, in [19], where an explicit algorithm for constructing a triangulation from a Heegaard diagram is provided.

Our second contribution investigates the interplay between the maximum edge valence and the treewidth of a 3-manifold triangulation $\mathcal{T}$. Analogous to the notion of vertex degree in graphs, the valence of an edge in $\mathcal{T}$ is defined as the number of tetrahedra in $\mathcal{T}$ that contain it. While treewidth can be viewed as a measure of global sparsity, the maximum edge valence captures local sparsity. The maximum edge valence of a triangulation can also provide valuable insights into geometric properties of the underlying 3-manifold [16, Sec. 3.6]. Having a triangulation $\mathcal{T}$ with small maximum edge valence can be computationally advantageous even when $\mathcal{T}$ already has small treewidth; see Appendix A for a discussion.

Every closed orientable 3-manifold has a triangulation with maximum edge valence at most six [4]. Frick has shown by an explicit construction that any triangulation $\mathcal{T}$ can be modified into a triangulation $\mathcal{T}^\dagger$ of the same manifold with edge valences at most nine [16, Theorem 3.36]. However, this construction may significantly increase the treewidth of the resulting triangulation, because if $\mathcal{T}$ contains edges with large valence, the retriangulation procedure introduces large grid-like structures in $\mathcal{T}^\dagger$. In Section 4, we show how to circumvent this and obtain a different retriangulation $\mathcal{T}^*$ that also achieves $\Delta(\mathcal{T}^*) \le 9$, while controlling the increase in treewidth by a polylogarithmic factor of the maximum edge valence of $\mathcal{T}$.

**Theorem 2.** There is an algorithm which, given a triangulation $\mathcal{T}$ of a closed 3-manifold $\mathcal{M}$ with $n$ tetrahedra, $v$ vertices, $\text{tw}(\Gamma(\mathcal{T})) = \text{tw}$, and maximum edge valence $\Delta(\mathcal{T}) = \Delta$, constructs a triangulation $\mathcal{T}^*$ of $\mathcal{M}$ with $O((n + v) \cdot \text{poly}(\log_2(\Delta)))$ vertices and tetrahedra, $\text{tw}(\Gamma(\mathcal{T}^*)) \le \text{tw} \cdot \text{poly}(\log_2(\Delta))$, and $\Delta(\mathcal{T}^*) \le 9$. The algorithm runs in $O(n \log \log n)$ time.

Finally, the execution of the algorithms in Theorem 2 and Theorem 1 (in this order) yields the following corollary, which we believe to be of independent interest.

<footnote>$^5$ The number $V(\mathcal{D})$ of vertices and the treewidth $\text{tw}(\mathcal{D})$ of a Heegaard diagram $\mathcal{D} = (S, \alpha, \beta)$ are, by definition, respectively equal to those of its underlying graph, which is the 4-regular multigraph geometrically obtained by taking the union of the $\alpha$- and $\beta$-curves and placing a vertex at each crossing.</footnote>
**► Corollary 3.** *There is a quasi-linear time algorithm that, given a triangulation $\mathcal{T}$ of a closed, orientable 3-manifold $\mathcal{M}$ with $n$ tetrahedra, $\text{tw}(\Gamma(\mathcal{T})) = \text{tw}$, and maximum edge valence $\Delta(\mathcal{T}) = \Delta$, constructs a Heegaard diagram $\mathcal{D} = (S, \alpha, \beta)$ of $\mathcal{M}$ of size and genus $O(n \text{ poly}(\log(\Delta)))$, treewidth $O(\text{tw} \cdot \text{poly}(\log(\Delta)))$, where any $\alpha$-curve intersects at most 9 $\beta$-curves, and any $\beta$-curve intersects at most 3 $\alpha$-curves.*

# 2 Preliminaries

## 2.1 Graphs and their treewidth

By a *graph* we generally mean a multigraph $G = (V, E)$ with a finite set $V = V(G)$ of *vertices* and of a multiset $E = E(G)$ of two-element submultisets of $V$ called *edges*. A *loop* is an edge of the form $\{v, v\}$, and a *multiedge* is an edge with multiplicity larger than one. A graph without loops or multiedges is *simple*. The degree $\deg(v)$ of $v \in V$ is the number of edges containing $v$, counted with multiplicity. A graph is $k$-regular if $\deg(v) = k$ for all $v \in V$.

Introduced in [42] (cf. [15]), the *treewidth* of a graph measures its similarity to any tree. A tree decomposition $\mathcal{X}$ of a graph $G = (V, E)$ is a pair $\mathcal{X} = (T, \mathcal{B})$ of a tree $T = (I, F)$ and a collection $\mathcal{B} = \{B_i : i \in I\}$ of *bags*, where $B_i \subseteq V$ and the following three properties hold: 1. $\cup_{i \in I} B_i = V$ (vertex coverage), 2. for every $\{u, v\} \in E$ there exists $i \in I$ with $\{u, v\} \subseteq B_i$ (edge coverage), and 3. for every $v \in V$, the set $T_v = \{i \in I : v \in B_i\}$ spans a connected subtree of $T$ (subtree property). The *width* of the tree decomposition $\mathcal{X}$ equals $\max_{i \in I} |B_i| - 1$, and the *treewidth* $\text{tw}(G)$ is defined as the smallest width of any tree decomposition of $G$.

## 2.2 3-Manifolds and their representations

A $d$-dimensional *topological manifold with boundary* (hereafter *d-manifold*) $\mathcal{M}$ is a topological space$^6$ locally homeomorphic to $\mathbb{R}^d$, i.e., every point of $\mathcal{M}$ has a neighborhood homeomorphic to $\mathbb{R}^d$ or to the upper half-space $\{(x_1, \dots, x_d) \in \mathbb{R}^d : x_d \ge 0\}$. The *boundary* $\partial \mathcal{M}$ of $\mathcal{M}$ consists of all points of $\mathcal{M}$ that have no open neighborhood homeomorphic to $\mathbb{R}^d$. In this paper we only consider compact, orientable $d$-manifolds with $d \le 3$. A manifold $\mathcal{M}$ is *closed* if it is compact and $\partial \mathcal{M} = \emptyset$. A *surface* is just a 2-manifold. We only consider compact orientable manifolds, and up to homeomorphism. See [45] for general background on 3-manifolds.

**Triangulations and their dual graphs** As is common in algorithmic topology, we define a (3-dimensional) *triangulation* as a quotient space $\mathcal{T} = \Sigma/\Phi$, where $\Sigma = \{\sigma_1, \dots, \sigma_n\}$ is a set of labeled and vertex-labeled abstract tetrahedra, and $\Phi = \{\varphi_1, \dots, \varphi_m\}$ is a set of simplicial isomorphisms, called *gluing maps*, each of which identifies two triangles of the simplices in $\Sigma$.⁷ For $i \in \{0, 1, 2, 3\}$, let $\mathcal{T}(i)$ denote the set of $i$-dimensional faces of the resulting quotient $\mathcal{T}$, and let $\mathcal{T}^{(i)}$, its $i$-skeleton, be $\mathcal{T}^{(i)} := \cup_{j=0}^i \mathcal{T}(j)$. The *valence* $\text{val}(e)$ of an edge $e \in \mathcal{T}(1)$ is the number of tetrahedra in $\mathcal{T}$ that contain it and $\Delta(\mathcal{T}) := \max_{e \in \mathcal{T}(1)} \text{val}(e)$. $\mathcal{T}$ *triangulates* the manifold $\mathcal{M}$ if (the geometric realization of) $\mathcal{T}$ is homeomorphic to $\mathcal{M}$. Triangulations of surfaces are defined analogously. Surfaces and 3-manifolds always be triangulated [39, 41].

Given a triangulation $\mathcal{T} = \Sigma/\Phi$, its *dual graph* (or *face-pairing graph*) $\Gamma(\mathcal{T})$ is the graph with $V(\Gamma(\mathcal{T})) = \Sigma$, and $\{\sigma_1, \sigma_2\} \in E(\Gamma(\mathcal{T}))$ if and only if there is a gluing map $\varphi \in \Phi$ that

<footnote>$^6$ Some technical requirements about the space are intentionally omitted here, cf. [45, Definition 1.1.1].</footnote>

<footnote>$^7$ Each triangle is identified with at most one other triangle. We allow two pairs of triangles to be glued between the same pair of tetrahedra, as well as gluing two triangles within a single tetrahedron. Hence the triangulations considered here are not simplicial complexes but *regular simplicial cell complexes*. Nevertheless, the second barycentric subdivision $\mathcal{T}''$ of any triangulation $\mathcal{T}$ is always a simplicial complex.</footnote>
4 On Sparse Representations of 3-Manifolds

identifies a triangle of $\sigma_1$ with a triangle of $\sigma_2$ (where $\sigma_1$ and $\sigma_2$ may coincide). See Figure 1.
We define the *treewidth of a triangulation $\mathcal{T}$ as the treewidth of its dual graph $\Gamma(\mathcal{T})$.

<figure><img src="image_8.png" /><figcaption>■ **Figure 1** A triangulation $\mathcal{T} = \Sigma/\Phi$ with tetrahedra $\Sigma = \{\sigma_1, \sigma_2\}$, gluing maps $\Phi = \{\varphi_1, \varphi_2, \varphi_3\}$ and dual graph $\Gamma(\mathcal{T})$. $\varphi_1$ is explicitly defined as $\sigma_1(123) \leftrightarrow \sigma_2(103)$. Based on [25, Figure 1].</figcaption></figure>

**Handlebodies and Heegaard splittings** A *handlebody* $\mathcal{H}$ is a compact 3-manifold homeomorphic to a regular neighborhood of a bouquet of circles embedded in $\mathbb{R}^3$. Every closed, orientable 3-manifold $\mathcal{M}$ admits a *Heegaard splitting* [20, 21], i.e., a decomposition into two homeomorphic handlebodies $\mathcal{H}_1$ and $\mathcal{H}_2$ with a shared boundary. That is, $\mathcal{M} = \mathcal{H}_1 \cup \mathcal{H}_2$ and $\mathcal{H}_1 \cap \mathcal{H}_2 = \partial\mathcal{H}_1 = \partial\mathcal{H}_2 = \mathcal{S}$. The surface $\mathcal{S}$ is called a *splitting surface*, and its genus $g(\mathcal{S})$ is referred to as the *genus of the Heegaard splitting*. The minimum genus of any Heegaard splitting of $\mathcal{M}$ is called the *Heegaard genus* of $\mathcal{M}$. We refer to [44] for an extensive survey.

**Heegaard diagrams** Heegaard diagrams were developed alongside Heegaard splittings to describe them. They also provide the basis for computing Kuperberg’s invariants (Section 5). We follow the definitions of [28, Section 4]. In particular, we consider Heegaard diagrams in a sense more flexible than usual. A *handlebody diagram* is an ordered pair $(\mathcal{S}, \gamma)$ of a closed orientable surface $\mathcal{S}$ and a collection $\gamma = \{\gamma_1, \dots, \gamma_l\}$ of pairwise disjoint simple closed curves embedded in $\mathcal{S}$ that divide $\mathcal{S}$ into planar regions.<fnref n="8" /> (Figure 2). A handlebody diagram $(\mathcal{S}, \gamma)$

<figure><img src="image_9.png" /><figcaption>■ **Figure 2** Illustrations of some handlebody diagrams. The surfaces are meant to be hollow.</figcaption></figure>

can be seen as a prescription for gluing a handlebody to one side of $\mathcal{S}$. Specifically, consider the thickening $\mathcal{S} \times [0, 1]$, and for each $i \in \{1, \dots, l\}$ attach to its *upper boundary* $\mathcal{S} \times \{1\}$ a thickened disk (called a *2-handle*) along the curve $\gamma_i$.<fnref n="9" /> Because of the assumption about $\gamma$, each resulting new boundary component is a 2-sphere, each of which we fill in with a 3-ball. (Importantly, these fillings are unique up to isotopy; see [45, Lemma 2.5.3].) The union of the attached 2-handles and the filling 3-balls is a handlebody $\mathcal{H}$, which we have just glued to $\mathcal{S}$.

With that, a *Heegaard diagram* is a triple $\mathcal{D} = (\mathcal{S}, \alpha, \beta)$ such that $(\mathcal{S}, \alpha)$ and $(\mathcal{S}, \beta)$ are handlebody diagrams relative to different sides of $\mathcal{S}$. That is, the 2-handles corresponding to

<footnote n="8">⁸ Because of this requirement the number $\ell$ of curves in $\gamma$ is at least the genus $g(\mathcal{S})$ of the surface $\mathcal{S}$, and $\ell = g(\mathcal{S})$ is commonly assumed in the literature. However, we will generally have $\ell > g(\mathcal{S})$.</footnote>

<footnote n="9">⁹ More precisely, we attach the 2-handle along the copy of $\gamma_i$ in $\mathcal{S} \times \{1\}$.</footnote>
$\alpha$ (resp. $\beta$) are attached to the upper boundary $S \times \{1\}$ (resp. the lower boundary $S \times \{0\}$) of the thickening $S \times [0, 1]$. We refer to the curves in $\alpha$ (resp. $\beta$) as $\alpha$-curves (resp. $\beta$-curves) and assign the same color to each family in illustrations; see Figure 3. A Heegaard diagram $\mathcal{D}$ can naturally be viewed as a 4-regular, surface-embedded graph, obtained geometrically by taking the union of the $\alpha$- and $\beta$-curves and placing a vertex at each crossing.

<figure><img src="image_10.png" /><figcaption>Figure 3 Two Heegaard diagrams of the 3-sphere, and one of the real projective 3-space $\mathbb{RP}^3$.</figcaption></figure>

### 3 From triangulations to Heegaard diagrams

In this section, we revisit a classical construction that converts a triangulation $\mathcal{T}$ into a corresponding Heegaard diagram $\mathcal{D} = (S, \alpha, \beta)$. We prove that this construction preserves both size and width up to a constant factor, as stated in Theorem 1. Moreover, using standard data structures, the conversion $\mathcal{T} \rightsquigarrow \mathcal{D}$ can be performed in time linear in the size of $\mathcal{T}$. We first review the construction via handles, then prove the inequalities (1a) and (1b) in Theorem 1, and finally discuss the algorithmic aspects of the construction.

**Handle decompositions** Any triangulation $\mathcal{T}$ of a 3-manifold $\mathcal{M}$ induces a *canonical handle decomposition chd(\mathcal{T})$* of $\mathcal{M}$, in which the *k-handles* (all 3-balls) correspond to the $(3-k)$-simplices of $\mathcal{T}$. Informally, chd($\mathcal{T}$) is the “thickening” of $\mathcal{T}$ (see Figure 4a). For each tetrahedron $\sigma \in \mathcal{T}(3)$, take a 0-handle centered at its barycenter. For each triangle $t \in \mathcal{T}(2)$, attach a 1-handle along a pair of disjoint disks connecting the 0-handles of the tetrahedra incident to $t$. For each edge $e \in \mathcal{T}(1)$, attach a 2-handle along an annulus to the union of the 0- and 1-handles corresponding to the tetrahedra and triangles incident to $e$. Finally, for each vertex $v \in \mathcal{T}(0)$, attach a 3-handle along a 2-sphere to fill the void surrounding $v$.

<figure><img src="image_11.png" /><figcaption>(a) The building blocks of the canonical handle decomposition chd($\mathcal{T}$). (b) The $\alpha$- and $\beta$-curves of $\mathcal{D}(\mathcal{T})$ restricted to a tetrahedron $\sigma$ of $\mathcal{T}$.
Meridian curves of the 1- and the 2-handle are also drawn.</figcaption></figure>

<caption>Figure 4</caption>

**The Heegaard diagram induced by $\mathcal{T}$** The union $\mathcal{H}_1$ of the 0- and 1-handles and the union $\mathcal{H}_2$ of the 2- and 3-handles of chd($\mathcal{T}$) are both handlebodies that together form a
6 On Sparse Representations of 3-Manifolds

Heegaard splitting of the 3-manifold triangulated by $\mathcal{T}$. Letting $\mathcal{S} := \mathcal{H}_1 \cap \mathcal{H}_2$ and taking the meridional curves of the 2-handles and those of the 1-handles as $\alpha$- and $\beta$-curves, respectively (Figure 4a), we obtain the Heegaard diagram $\mathcal{D}(\mathcal{T}) = (\mathcal{S}, \alpha, \beta)$, where $\alpha = \{\alpha_e : e \in \mathcal{T}(1)\}$ and $\beta = \{\beta_t : t \in \mathcal{T}(2)\}$. We call $\mathcal{D}(\mathcal{T})$ the Heegaard diagram induced by the triangulation $\mathcal{T}$.

**Proof of inequalities (1a) and (1b) in Theorem 1.** For (1a), note that each triangle of $\mathcal{T}$ contains exactly three vertices of the Heegaard diagram $\mathcal{D} := \mathcal{D}(\mathcal{T})$ induced by $\mathcal{T}$ (Figure 4b), and each tetrahedron has four triangular faces identified in pairs, hence $|V(\mathcal{D})| = 3 \cdot 4n/2 = 6n$. To show (1b), take an optimal tree decomposition $\mathcal{X} = (T, \mathcal{B})$ of $\Gamma(\mathcal{T})$, where $T = (I, F)$ is a tree, $\mathcal{B} = \{B_i : i \in I\}$ is the corresponding set of bags, and $\max\{|B_i| : i \in I\} = \text{tw}(\Gamma(\mathcal{T})) + 1$. We turn $\mathcal{X}$ into a tree decomposition $\mathcal{X}' = (T', \mathcal{B}')$ of $\mathcal{D}$ as follows.

- $T' = T$, i.e., the tree structure of the decomposition remains the same.

- $\mathcal{B}' = \{B'_i : i \in I\}$ and for each $i \in I$, the bag $B'_i$ is obtained from $B_i$ by replacing each $\sigma \in B_i$ with the (at most) 12 vertices of $\mathcal{D}$ incident to $\sigma$, see Figure 4b.

Clearly, $|B'_i| \le 12|B_i|$. We now check that $\mathcal{X}' = (T', \mathcal{B}')$ is a tree decomposition of $\mathcal{D}$.

**Vertex coverage** Consider a vertex $v \in V(\mathcal{D})$. By construction, there exists a tetrahedron $\sigma \in \mathcal{T}$, such that $v$ is incident to $\sigma$. Thus, for any $i \in I$, $v \in B'_i \Leftrightarrow \sigma \in B_i$. However, since $\bigcup_{i \in I} B_i = V(\Gamma(\mathcal{T}))$, this implies $\bigcup_{i \in I} B'_i = V(\mathcal{D})$ as well.

**Edge coverage** Let $e = \{u, v\} \in E(\mathcal{D})$ be any arc of the diagram. Again, by construction of $\mathcal{D}$, there exists a tetrahedron $\sigma \in \mathcal{T}$ that entirely contains $e$. Let $B_i$ be a bag that contains $\sigma$. Then $B'_i$ must contain both $u$ and $v$.

**Subtree property** Fix a vertex $v \in V(\mathcal{D})$ and consider $I'_v := \{i \in I : v \in B'_i\}$. We need to show that $I'_v$ spans a connected subtree of $T' = T$. Let $\sigma, \tau \in \mathcal{T}$ be the tetrahedra containing $v$ on their common triangular face (note that $\sigma$ and $\tau$ may coincide) and define $I_\sigma := \{i \in I : \sigma \in B_i\}$ and $I_\tau := \{i \in I : \tau \in B_i\}$. From the definition of $\mathcal{B}'$ it follows that $I'_v = I_\sigma \cup I_\tau$. Since $\mathcal{X}$ is a tree decomposition of $\Gamma(\mathcal{T})$, each of $I_\sigma$ and $I_\tau$ spans a connected subtree in $T'$. Moreover, $I_\sigma \cap I_\tau \ne \emptyset$: either $\sigma = \tau$, or $\{\sigma, \tau\} \in E(\Gamma(\mathcal{T}))$, so there exists a bag $B_j$ containing both $\sigma$ and $\tau$. Thus, the connected subtrees spanned by $I_\sigma$ and $I_\tau$ overlap, hence their union $I'_v$ spans a connected subtree as well. $\quad$

**Algorithmic aspects of Theorem 1** We briefly comment on the computational cost of extracting the Heegaard diagram $\mathcal{D}(\mathcal{T})$ from a given triangulation $\mathcal{T}$ with $n$ tetrahedra. Recall that for an abstract simplicial complex $\mathcal{C}$, its barycentric subdivision $\mathcal{C}'$ is the simplicial complex whose ground set is $\mathcal{C}$, and a collection $\{\tau_0, \dots, \tau_k\}$ forms a $k$-simplex in $\mathcal{C}'$ precisely when the simplices $\tau_i \in \mathcal{C}$ are nested, that is, when $\tau_0 \subset \dots \subset \tau_k$. Although a triangulation $\mathcal{T}$ is generally not a simplicial complex, we can still form its barycentric subdivision by first subdividing each tetrahedron and then applying the gluing maps to identify the subdivided triangular faces. Performed twice, the resulting complex $\mathcal{T}''$ naturally contains both the canonical handle decomposition chd($\mathcal{T}$) and the induced Heegaard diagram $\mathcal{D}(\mathcal{T})$. As the barycentric subdivision of a tetrahedron contains $24$ tetrahedra, $|\mathcal{T}''| = 24^2|\mathcal{T}| = 576|\mathcal{T}|$.

**Extracting chd($\mathcal{T}$) from $\mathcal{T}''$** Every vertex $v$ of $\mathcal{T}'$ is of the form $v = \{\tau\}$ for some simplex $\tau \in \mathcal{T}$. Let $\iota: \mathcal{T}'(0) \to \mathcal{T}''(0)$ be the natural inclusion defined by $\iota(\{\tau\}) = \{\{\tau\}\}$. For every $w \in \text{im}(\iota)$, let $h_w$ be the smallest subcomplex of $\mathcal{T}''$ containing all 3-faces incident to $w$. If $w$ corresponds to a simplex $\sigma \in \mathcal{T}$ of dimension $3-k$, then $h_w$ is regarded as a $k$-handle. The collection $\{h_w : w \in \text{im}(\iota)\}$ forms the canonical handle decomposition chd($\mathcal{T}$). See Figure 5.
<figure><img src="image_12.png" /><figcaption>■ **Figure 5** A 2-dimensional triangulation $\mathcal{T}$ with two triangles, its first and second barycentric subdivisions $\mathcal{T}'$ and $\mathcal{T}''$ (regarded geometrically), and the canonical handle decomposition $\text{chd}(\mathcal{T})$.</figcaption></figure>

**Extracting $\mathcal{D}(\mathcal{T})$ from $\mathcal{T}''$** To extract the induced Heegaard diagram $\mathcal{D}(\mathcal{T})$ from $\mathcal{T}''$, we need to pinpoint its $\alpha$- and $\beta$-curves, as well as the splitting surface $\mathcal{S}$ in $\mathcal{T}''$. We illustrate this via concrete examples; see Figure 6. We start with the $\alpha$-curves. Let $e \in \mathcal{T}(1)$ be an edge of $\mathcal{T}$, and assume that $e$ is contained in four distinct tetrahedra $\sigma_1, \sigma_2, \sigma_3, \sigma_4$ of $\mathcal{T}$. Let $t_{ij}$ denote the triangular face shared by $\sigma_i$ and $\sigma_j$. Consider the subcomplex $C_e$ of $\mathcal{T}'$ spanned by the nine vertices $\{e\}, \{\sigma_1\}, \{\sigma_2\}, \{\sigma_3\}, \{\sigma_4\}, \{t_{12}\}, \{t_{23}\}, \{t_{34}\},$ and $\{t_{14}\}$. This complex $C_e$ triangulates the *dual* 2-cell transverse to $e$ (Figure 6, top left). Taking the second barycentric subdivision $\mathcal{T}''$ (Figure 6, top middle), we see that the $\alpha$-curve $\alpha_e$ corresponding to $e$ is readily obtained as the polygonal curve spanned by the vertices of $C_e'$ adjacent to $\{{\{e}\}\}$ (Figure 6, top right). The $\beta$-curves can be located analogously (Figure 6, bottom row).

<figure><img src="image_13.png" /><figcaption>■ **Figure 6** Locating the $\alpha$- and $\beta$-curves $\mathcal{D}(\mathcal{T})$ in the second barycentric subdivision $\mathcal{T}''$ of $\mathcal{T}$.</figcaption></figure>

A triangulation of the splitting surface $\mathcal{S}$ can also be readily obtained as the boundary of the subcomplex of $\mathcal{T}''$ formed by the union of the triangulated 2- and 3-handles of $\text{chd}(\mathcal{T})$. Using standard data structures to represent these objects (such as in *Regina* [7]), all of these operations can be performed in linear time in terms of $n = |\mathcal{T}|$.
► **Remark 4.** Often it is assumed—and in certain applications even required, cf. [29]—that a Heegaard diagram $\mathcal{D} = (S, \alpha, \beta)$ be minimal, i.e. $|\alpha| = |\beta| = g(S)$. In our setting, we can ensure this by first choosing arbitrary spanning trees $T_1$ and $T_2$ for the 1-skeleton $\mathcal{T}^{(1)}$ and the dual graph $\Gamma(\mathcal{T})$ of $\mathcal{T}$, respectively, and then retaining only those $\alpha$-curves (resp. $\beta$-curves) that correspond to edges of $\mathcal{T}^{(1)}$ (resp. $\Gamma(\mathcal{T})$) not contained in $T_1$ (resp. $T_2$).

## 4 Retriangulating with constant edge valence and controlled treewidth

In this section, we describe and analyze a quasi-linear time procedure that retriangulates any 3-manifold triangulation $\mathcal{T}$ into a triangulation $\mathcal{T}^*$ with maximum edge valence at most 9 and treewidth increased only by a polylogarithmic factor of the original maximum edge valence.

► **Theorem 5 (Theorem 2; with explicit polylog-factors).** There is an algorithm which, given a triangulation $\mathcal{T}$ of a closed 3-manifold $\mathcal{M}$ with $n$ tetrahedra, $\mathbf{v}$ vertices, $\mathrm{tw}(\Gamma(\mathcal{T})) = \mathbf{tw}$, and maximum edge valence $\Delta(\mathcal{T}) = \mathbf{\Delta}$, yields a triangulation $\mathcal{T}^*$ of $\mathcal{M}$ with $O((n+\mathbf{v})\log_2(\mathbf{\Delta})^{5.32})$ vertices and tetrahedra, $\mathrm{tw}(\Gamma(\mathcal{T}^*)) < (\mathbf{tw}+1) \cdot \log_2(\mathbf{\Delta})^{5.17}$, and $\Delta(\mathcal{T}^*) \le 9$. The algorithm runs in $O(n \log \log n)$ time.

The construction in Theorem 5 is based on an iterative application of the following result.

► **Theorem 6.** There is an algorithm which, given a triangulation $\mathcal{T}$ of a closed 3-manifold $\mathcal{M}$ with $n$ tetrahedra, $\mathbf{v}$ vertices, $\mathrm{tw}(\Gamma(\mathcal{T})) = \mathbf{tw}$, and $\Delta(\mathcal{T}) = \mathbf{\Delta}$, constructs a triangulation $\mathcal{T}^*$ of $\mathcal{M}$ with at most $(28+4\sqrt{6})n + (16+4\sqrt{6})\mathbf{v}$ tetrahedra, $(6+\sqrt{6})(n+\mathbf{v})$ vertices, $\Delta(\mathcal{T}^*) \le \max\{\lceil\sqrt{\mathbf{\Delta}}\rceil + 4, 9\}$, and $\mathrm{tw}(\Gamma(\mathcal{T}^*)) \le 36 \cdot \mathbf{tw}$. The algorithm runs in $O(n)$ time.

The proof of Theorem 6 is the core of this section. We prove Theorem 5 at the end of it.

**Setup** Let us fix a triangulation $\mathcal{T}$ of a closed 3-manifold $\mathcal{M}$ with $n$ tetrahedra, $|\mathcal{T}(0)| = \mathbf{v}$ vertices, treewidth $\mathrm{tw}(\Gamma(\mathcal{T})) = \mathbf{tw}$, and maximum edge valence $\Delta(\mathcal{T}) = \mathbf{\Delta}$. Let $S = S(\mathcal{T})$ be the spine of $\mathcal{M}$ dual to $\mathcal{T}$. It is a 2-dimensional polyhedral cell complex whose 1-skeleton $S^{(1)}$ is the dual graph $\Gamma(\mathcal{T})$, and for each edge $e \in \mathcal{T}(1)$, $S$ contains a polygonal 2-face $F_e$ glued along the cycle in $\Gamma(\mathcal{T})$ formed by the vertices corresponding to the tetrahedra that contain $e$. Locally, at each tetrahedron of $\mathcal{T}$, the spine $S$ looks like the configuration shown in Figure 7.

► **Remark.** Spines, and in particular *special spines*, offer a perspective on 3-manifolds that is dual to that provided by triangulations. We refer to [38, Chapter 1] and [43] for details.

**Overall strategy** Note that, given the spine $S$, we can recover $\mathcal{M}$ by first thickening $S$ and then filling in the resulting 2-sphere boundary components with 3-balls (which may be viewed as centered at the vertices of $\mathcal{T}$). In what follows, we triangulate $S$ and fill in these missing balls combinatorially. Throughout, the term 2-face refers to the faces of the spine $S$, whereas *triangle* refers to the faces of the triangulation. Our strategy is similar to that of [16, Theorem 3.36], but we employ a different—and necessarily more intricate—triangulation of the 2-faces of $S$ in order to control the treewidth of the resulting triangulation.

**Triangulating the faces of S** Consider a 2-face $F := F_e$ of the spine $S$ transverse to an edge $e \in \mathcal{T}(1)$. This face $F$ is a $k$-gon, where $k = \mathrm{val}(e)$, whose vertices are the centers of the tetrahedra of $\mathcal{T}$ containing $e$. We triangulate $F$ as follows (see Figure 8). If $k \le 9$, we add a vertex $w$ at the center of $F$ and connect it to all boundary vertices, as in Figure 8 (left). If $k > 9$, we proceed as follows. Fix an arbitrary orientation of the boundary of $F$, and choose positive integers $m := m_F$ and $d := d_F$ such that $k \le m(d-1)$. Label the boundary vertices
<figure><img src="image_14.png" /><figcaption>■ **Figure 7** The intersection of the spine $S$ with a tetrahedron of $\mathcal{T}$. The vertices of $S$ bijectively correspond to the centers of tetrahedra of $\mathcal{T}$, and each 2-face of $S$ is transverse to an edge of $\mathcal{T}$.</figcaption></figure>

$u_0, \dots, u_{k-1}$ in accordance with this orientation. Introduce a ring of $m$ interior vertices $v_0, \dots, v_{m-1}$, and connect each $v_i$ to $v_{i-1}$ and $v_{i+1}$ (indices mod $m$). For each $0 \le i < m-1$, connect $v_i$ to the boundary vertices $u_{i(d-1)}, \dots, u_{i+1}(d-1)$. The final interior vertex $v_{m-1}$ is connected to $u_{(m-1)(d-1)}, \dots, u_{k-1}, u_0$. The inequalities $(m-1)(d-1) < k \le m(d-1)$ ensure that the vertices $u_i$ and $v_i$, together with these edges, form a triangulated annulus. Finally, we place a central vertex $w$ inside $F$ and connect it to all $v_i$, see Figure 8 (right).

The next proposition follows directly from this construction; $k$, $m$, and $d$ are as above.

**Proposition 7.** The triangulation of the 2-face $F$ described above consists of $k + 2m$ triangles. Each boundary vertex $u_i$ is incident to 3 or 4 edges, each interior vertex $v_j$ is incident to at most $d+3$ edges, and the central vertex $w$ is incident to $m$ edges. In particular, the maximum degree of a vertex in the 1-skeleton of $F$ is $\max\{m, d+3\}$.

**Building the triangulation $\mathcal{T}^*$ in Theorem 6** Let $\mathcal{T}_S$ denote the triangulation of the spine $S$ obtained by triangulating each 2-face $F$ of $S$ as described above. We construct the triangulation $\mathcal{T}^*$ by first taking $\mathcal{T}_S$, considered as embedded in the geometric realization $\|\mathcal{T}\|$ of $\mathcal{T}$, and then adding the vertices $\mathcal{T}(0)$. Each vertex $a \in \mathcal{T}(0)$ lies in the interior of a connected component of $\|\mathcal{T}\| \setminus S$, which is an open 3-ball denoted by $B_a$. Its boundary $\partial B_a := \bar{B}_a \setminus B_a$ is a subpolyhedron of $S$ comprised of certain 2-faces of $S$. Let $\mathcal{T}_{\partial B_a}$ denote the subtriangulation of $\mathcal{T}_S$ formed by the union of the triangulations of these 2-faces of $S$. To complete the construction, for each $a \in \mathcal{T}(0)$ we cone over $\mathcal{T}_{\partial B_a}$ from the vertex $a$. We denote the resulting triangulation by $\mathcal{T}^*$. By construction, $\mathcal{T}^*$ triangulates $M$.

**Remark.** In the above construction, for each 2-face $F$ we fix integers $m = m_F$ and $d = d_F$ that depend solely on the number of boundary vertices $u_i$ of $F$ in $S$, or equivalently, on the valence of the edge of $\mathcal{T}$ transverse to $F$. When the context requires, we write $d_F$ and $m_F$.

**Definition 8 (type of a vertex of $\mathcal{T}^*$).** The vertices of $\mathcal{T}^*$ fall into the following three types. 1. vertices $a \in \mathcal{T}(0)$, 2. vertices $u_i$ lying on the boundary of exactly six 2-faces of $S$, and 3. vertices $v_i$ and $w$ lying in the interior of exactly one 2-face of $S$.

We proceed with investigating the maximum edge valence and the treewidth of $\mathcal{T}^*$.

**Lemma 9.** The triangulation $\mathcal{T}^*$ has edge valences at most $\max_{F \in S} \max\{d_F + 3, m_F, 9\}$.
<figure><img src="image_15.png" /><figcaption>Figure 8 Triangulating a 2-face $F$ (a $k$-gon) of the spine $S$ of $\mathcal{T}$ if $k \le 9$ (left) and if $k > 9$ (right).</figcaption></figure>

**Proof.** We consider, case by case, the different types of edges in $\mathcal{T}^*$. Let $a$ denote a vertex of $\mathcal{T}(0)$, and let $u_i, v_\ell$, and $w$ denote vertices in a 2-face $F$, see Figure 8. (We keep this labeling convention throughout this section.) The next valence-bounds follow from Proposition 7.

*Type {a, w}* The valence of the edge of this type is equal to the degree of $w$ in the triangulation of the 2-face, i.e., $\text{val}(\{a, w\}) = m$.

*Type {a, v_ℓ}* The valence of the edge of this type is equal to the degree of $v_ℓ$ in the triangulation of the 2-face, i.e., $d+3$.

*Type {a, u_i}* is incident to at most 3 tetrahedra per 2-face containing $u_i$, and there are at most three 2-faces containing $u_i$ and bounding the ball containing $a$, so $\text{val}(\{a, u_i\}) \le 9$.

*Type {w, v_ℓ}* or {v_ℓ, u_i} are incident to at most 4 tetrahedra, two on either side of $F$,

*Type {u_i, u_{i+1}}* is incident to one tetrahedra {$a, v_\ell, u_i, u_{i+1}$} per 2-face that contains it, and is contained in at most three 2-faces, therefore $\text{val}(\{u_i, u_{i+1}\}) \le 3$.

Hence, for the maximum edge valence of $\mathcal{T}^*$ we have $\Delta(\mathcal{T}^*) \le \max\{d_F + 3, m_F, 9\}$. ◀

► **Lemma 10.** *The dual graph of the triangulation $\mathcal{T}^*$ has treewidth $\text{tw}(\Gamma(\mathcal{T}^*)) < 36 \cdot (\text{tw}+1)$.*

**Proof.** Consider a tree decomposition $\mathcal{X} = (T, \mathcal{B})$ of the graph $\Gamma(\mathcal{T})$ with optimal width $\text{tw}$.

By construction, every tetrahedron of $\mathcal{T}^*$ contains a vertex of $\mathcal{T}(0)$ and at least one triangle from the triangulation of a 2-face $F$ of $S$. Following the notation of Figure 8, these triangles are of the form $\{v_\ell, u_{i-1}, u_i\}$, $\{v_{\ell-1}, u_{\ell(d-1)}, v_{\ell+1}\}$, or $\{w, v_{\ell-1}, v_\ell\}$. For any 2-face of $S$, the boundary vertices $u_0, \dots, u_{k-1}$ correspond to nodes of the graph $\Gamma(\mathcal{T})$, and consequently each of them appears in some bag of this tree decomposition $\mathcal{X}$.
We now construct a tree decomposition $\mathcal{X}' = (T, \mathcal{B}')$ for the dual graph of $\mathcal{T}^*$, with the same underlying tree $T$ as for $\mathcal{X}$ and $\mathcal{B}' = \{B'_{\tau} : \tau \in V(T)\}$. We initialize $B'_{\tau}$ as $B'_{\tau} = \emptyset$ for all $\tau \in V(T)$, and consider all types of tetrahedra $\sigma$ in $\mathcal{T}^*$:

1. If $\sigma$ has a triangular face $\{v_\ell, u_{\ell-1}, u_i\}$, then add $\sigma$ to all bags $B'_{\tau}$ such that $u_{\ell-1} \in B_{\tau}$.

2. If $\sigma$ has a face $\{v_{\ell-1}, u_{\ell(d-1)}, v_{\ell+1}\}$, then add $\sigma$ to all bags $B'_{\tau}$ such that $u_{\ell(d-1)} \in B_{\tau}$. Similarly, for $\sigma = \{a, v_{m-1}, u_0, v_0\}$, add $\sigma$ to all bags $B'_{\tau}$ such that $u_0 \in B_{\tau}$.

3. If $\sigma$ has a face $\{w, v_{\ell-1}, v_\ell\}$, then add $\sigma$ to all bags $B'_{\tau}$ such that $B_{\tau}$ contains any $u_i$ with $\ell(d-1) \le i < \max\{(\ell+1)(d-1), k-1\}$.

<figure><img src="image_16.png" /><figcaption>**Figure 9** Illustrations of 7 possible triangles shared by tetrahedra in $\mathcal{T}^*$ from the proof of Claim 11.</figcaption></figure>

▷ Claim 11. $\mathcal{X}' = (T, \mathcal{B}')$ is a valid tree decomposition of the dual graph $\Gamma(\mathcal{T}^*)$ of $\mathcal{T}^*$.

*Proof.* We verify the three defining properties of a tree decomposition (Section 2.1).

**Vertex coverage** By construction, any tetrahedron of $\mathcal{T}^*$ contains a triangle from a 2-face $F$ of the spine $S$, and in consequence appears in some bag of $\mathcal{X}' = (T, \mathcal{B}')$.
**Edge coverage** Showing that every edge of $\mathcal{T}^*$ is contained in some bag of $\mathcal{X}'$ can be carried out by a tedious case analysis. In the triangulation $\mathcal{T}^*$, two tetrahedra may be adjacent along seven types of shared triangles, classified by the types of the triangle's vertices; all possible configurations are shown in Figure 9. See Appendix B for all the details.

**Subtree property** By 1 and 2, tetrahedra of type $\{a, v_\ell, u_i, u_{i+1}\}$, $\{a, v_{\ell-1}, u_{\ell(d-1)}, v_\ell\}$ and $\{a, v_{m-1}, u_0, v_0\}$ appear exactly in the bags $B_\tau'$ such that $B_\tau$ contain a certain fixed tetrahedron (respectively $u_i$, $u_{\ell(d-1)}$, and $u_0$); the bags containing them are consequently connected in $\sigma$. By 3, a tetrahedron $\sigma$ of type $\{a, w, v_{\ell-1}, v_\ell\}$ is inserted in all bags $B_\tau'$ such that $B_\tau$ contains any $u_i$ with $\ell(d-1) \le i < (\ell+1)(d-1)$. Call $T_i$ the subtree of $T$ spanned by the nodes $\tau$ such that $u_i \in B_\tau$ in $\mathcal{X}$. The subtree of $T$ spanned by the nodes $\tau$ in $\mathcal{X}'$ such that $\sigma \in B_\tau$ is, in consequence, $\cup_{\ell(d-1) \le i < (\ell+1)(d-1)} T_i$. Because $\mathcal{X}$ is a tree decomposition, each $T_i$ is connected. Additionally, for any $i$, $u_i$ and $u_{i+1}$ are adjacent, and must consequently appear in a common bag of $\mathcal{X}$. Hence $T_i \cap T_{i+1} \ne \emptyset$. In consequence, $\cup_{\ell(d-1) \le i < (\ell+1)(d-1)} T_i$ is a connected subtree of $\sigma$. $\triangleleft$

▷ Claim 12. $\mathcal{X}' = (T, \mathcal{B}')$ has width less than $36 \cdot (\mathbf{tw} + 1)$.

*Proof.* Let $B_\tau$ be a bag of $\mathcal{X}$ of size $r$. Every occurrence of a tetrahedron $u_i$ in $B_\tau$ will induce the insertion of at most 6 tetrahedra in $B_\tau'$, per 2-face incident to $u_i$, namely tetrahedra $(\star, v_\ell, u_i, u_{i+1})$, tetrahedra $(\star, v_\ell, u_i, v_{\ell+1})$ if $i = \ell(d-1)$ or $i = 0$, and tetrahedra $(\star, w, v_{\ell-1}, v_\ell)$ with $\ell(d-1) \le i \le \max\{(\ell+1)(d-1)-1, k-1\}$; where $\star$ indicates at most two possible vertices $a$ and $b$ of $\mathcal{T}(0)$, on either side of the 2-face. Adding the fact that at most six 2-faces are incident to a given tetrahedron $u_i$, the size of a bag $B_\tau'$ is at most 36 times the size of $B_\tau$. In consequence, the width of $\mathcal{X}'$ is at most $36 \cdot (\mathbf{tw} + 1) - 1$. This concludes the proofs of Claim 12 and Lemma 10. $\quad$

From now on, for the 2-face $F_e$ transverse to the edge $e \in \mathcal{T}(1)$ with valence $k = \text{val}(e)$, we set $m := \lfloor\sqrt{\text{val}(e)}\rfloor + 4$ and $d := \lfloor\sqrt{\text{val}(e)}\rfloor + 1$, which satisfy the condition $k \le m(d-1)$ whenever $\text{val}(e) > 6$. The next two lemmas provide bounds on the number of tetrahedra (Lemma 13) and the number of vertices (Lemma 14) in $\mathcal{T}^*$. These rely on standard counting arguments for triangulations; see Appendix C.2.

**Lemma 13.** *The triangulation $\mathcal{T}^*$ has at most $(28 + 4\sqrt{6})n + (16 + 4\sqrt{6})\mathbf{v}$ tetrahedra.*

*Proof.* Each 2-face, transversal to an edge $e$ of valence $\text{val}(e)$, contributes to $2(k+2m) = 2\text{val}(e) + 4(\lfloor\sqrt{\text{val}(e)}\rfloor + 4)$ tetrahedra ($k+2m$ triangles in the transversal 2-face $F$, holding a tetrahedron on either side of $F$). In consequence,

$$ \sum_{e \in \mathcal{T}(1)} (2 \operatorname{val}(e) + 4(\lfloor \sqrt{\operatorname{val}(e)} \rfloor + 4)) \stackrel{\text{Lem. 24, Cor. 25}}{\le} 12n + 16(n + \mathbf{v}) + 4 \sum_e \sqrt{\operatorname{val}(e)} $$

$$ \stackrel{\text{Lem. 26}}{\le} 12n + 16(n + \mathbf{v}) + 4\sqrt{6}(n + \mathbf{v}). \quad \triangleleft $$

**Lemma 14.** *The triangulation $\mathcal{T}^*$ has at most $(6 + \sqrt{6})(n + \mathbf{v})$ vertices.*

*Proof.* By construction, the vertex set $\mathcal{T}^*(0)$ consist of the vertices $\mathcal{T}(0)$, the vertices $u_i$ (lying on the boundaries of the 2-faces), and, for each $e \in \mathcal{T}(1)$, the $\lfloor\sqrt{\text{val}(e)}\rfloor + 5$ interior vertices on the triangulated 2-face $F_e$. The vertices $u_i$ are in bijection with the tetrahedra of $\mathcal{T}$, hence there are exactly $n$ of them. The total number of interior vertices over all 2-faces is

$$ \sum_{e \in \mathcal{T}(1)} (\lfloor \sqrt{\text{val}(e)} \rfloor + 5) \stackrel{\text{Lemmas 24, 26}}{\le} (\sqrt{6} + 5)(n + \mathbf{v}). $$

With $|\mathcal{T}(0)| = \mathbf{v}$ and the $n$ vertices $u_i$, this gives at most $(6 + \sqrt{6})(n + \mathbf{v})$ vertices in $\mathcal{T}^*$. $\quad$
We are now ready to prove the main theorems of this section.

**Proof of Theorem 6.** If the maximum edge valence of $\mathcal{T}$ is at most 9, the algorithm simply returns $\mathcal{T}^* := \mathcal{T}$. Otherwise, we apply the construction described above; the bounds on the number of tetrahedra, the number of vertices, the treewidth, and the edge valence follow from Lemmas 13, 14, 10, and 9, respectively. Note that the construction runs in time linear in the size of $\mathcal{T}^*$, which is $O(n)$. ◀

Finally, the proof of Theorem 5 relies on standard calculations involving geometric series and iterated radicals, as detailed in Lemmas 21, 22, and 23 in Appendix C.1.

**Proof of Theorem 5.** If the maximum edge valence of $\mathcal{T}$ satisfies $\Delta(\mathcal{T}) \le 9$, we are done. Otherwise, we construct a sequence of triangulations $\mathcal{T} = \mathcal{T}_0, \mathcal{T}_1, \dots, \mathcal{T}_p$ by iterating the construction of Theorem 6. The triangulation $\mathcal{T}_r$ has $O((30 + 4\sqrt{6})^r(n + \mathbf{v}))$ tetrahedra and vertices (Lemma 23), treewidth $\mathrm{tw}(\Gamma(\mathcal{T}_r)) < 36^r \cdot (\mathbf{tw} + 1)$ (Lemma 10), and maximum edge valence $\Delta(\mathcal{T}_r) \le \max\{a_r, 9\}$ (Lemma 9, with $m = \lfloor\sqrt{\mathrm{val}(e)}\rfloor + 4$ and $d = \lfloor\sqrt{\mathrm{val}(e)}\rfloor + 1$), where $(a_r)_{r \in \mathbb{N}}$ is the sequence of iterated radicals of Lemma 21, with $a_0 = \mathbf{\Delta}$, $c = 4$, and $L < 6.32$. By Lemma 22, choosing $p = \log_2 \log_2(\mathbf{\Delta})$ ensures that the edge valence of $\mathcal{T}_p$ is at most 9. We therefore set $\mathcal{T}^* := \mathcal{T}_p$. Since $\log_2(30 + 4\sqrt{6}) < 5.32$ and $\log_2(36) < 5.17$, the triangulation $\mathcal{T}^*$ has $O((n + \mathbf{v}) \log_2(\mathbf{\Delta}))^{5.32}$ tetrahedra and vertices, treewidth at most $(\mathbf{tw} + 1) \cdot \log_2(\mathbf{\Delta})^{5.17}$, and edge valence at most 9. The algorithm performs $O(\log \log(n))$ iterations of the algorithm of Theorem 6, yielding the stated complexity bound. ◀

# 5 Efficient evaluation of Kuperberg's tensor networks

In this section we present a fixed-parameter tractable (FPT) scheme for computing Kuperberg's quantum invariants $\#(\tilde{\mathcal{D}}, \mathcal{H})$ of closed, oriented$^{10}$ 3-manifolds [28]. This quantity depends on an oriented Heegaard diagram$^{11}$ $\tilde{\mathcal{D}} = (\tilde{S}, \tilde{\alpha}, \tilde{\beta})$ and a finite-dimensional involutory Hopf algebra $\mathcal{H}$ over a field $\mathbb{F}$, which is considered fixed. By construction, $\#(\tilde{\mathcal{D}}, \mathcal{H}) \in \mathbb{F}$.

► **Remark.** We emphasize that understanding the results in this section does **not** require knowledge of Hopf algebras or tensors, since the following proofs are purely graph theoretical. Nevertheless, we provide some basic definitions and examples in Appendix D. We refer to Kuperberg's paper [28] (cf. its open-access version [27]) for further details.

Even if $\#(\tilde{\mathcal{D}}, \mathcal{H})$ is originally derived from an oriented Heegaard diagram, it can also be computed from an oriented triangulation. This is briefly hinted at in [28, Section 4], however, with the machinery developed in Section 3 we can make it fully explicit: Any triangulation $\mathcal{T}$ of a 3-manifold $\mathcal{M}$ gives rise to a Heegaard diagram $\mathcal{D} = (\mathcal{S}, \alpha, \beta)$ of $\mathcal{M}$, moreover, in a width-preserving way (Theorem 1). Picking an orientation for $\mathcal{T}$ induces an orientation also for $\mathcal{S}$. Then choosing orientations for the $\alpha$- and $\beta$-curves arbitrarily yields an oriented diagram $\tilde{\mathcal{D}}$. Next, from $\tilde{\mathcal{D}}$ we build a tensor network $\mathcal{K}$ following Kuperberg's construction [28, Section 5], which we finally evaluate to obtain $\#(\tilde{\mathcal{D}}, \mathcal{H})$. From now on, we will use the notation $\#(\tilde{\mathcal{T}}, \mathcal{H}) := \#(\tilde{\mathcal{D}}, \mathcal{H})$ to indicate when we regard the invariant as computed from a triangulation, where $\tilde{\mathcal{D}}$ denotes the oriented Heegaard diagram induced by $\tilde{\mathcal{T}}$.

<footnote>$^{10}$In this section we assume $\mathcal{M}$ to be an *oriented*, not merely *orientable*, 3-manifold.</footnote>

<footnote>$^{11}$An *oriented Heegaard diagram* is a Heegaard diagram $\mathcal{D} = (\mathcal{S}, \alpha, \beta)$ together with an orientation for the surface $\mathcal{S}$ and for each of the $\alpha$- and $\beta$-curves. The quantity $\#(\tilde{\mathcal{D}}, \mathcal{H})$ does not depend on the choice of orientation for the $\alpha$- and $\beta$-curves, however, it generally does depend on the chosen orientation for $\mathcal{S}$.</footnote>
Building on Theorem 1 and bounding the treewidth of the tensor network $\mathcal{K}$ (Lemma 18), together with work of O’Gorman [40] (cf. Markov–Shi [37]) we prove the following result:

**Theorem 15.** Let $\mathcal{H}$ be a fixed finite-dimensional involutory Hopf algebra over a field $\mathbb{F}$. Let $\vec{\mathcal{T}}$ be an oriented triangulation of a closed oriented 3-manifold with $n$ tetrahedra and treewidth $\mathrm{tw}(\vec{\mathcal{T}}) := \mathrm{tw}(\Gamma(\vec{\mathcal{T}})) = t$. The invariant $\#(\vec{\mathcal{T}}, \mathcal{H})$ can be computed in time $O(2^{O(t)n})$.

Before discussing the proof of Theorem 15 in detail, we provide an overview on Figure 10.

<figure><img src="image_17.png" /><figcaption>■ **Figure 10** The algorithmic pipeline of computing $\#(\vec{\mathcal{T}}, \mathcal{H})$ from an oriented triangulation $\vec{\mathcal{T}}$. The references on the arrows provide the theoretical backbone, and the framed results indicate our contributions. The running time of the computation is dominated by that of step 3. $\mathcal{K} \to \#(\vec{\mathcal{T}}, \mathcal{H})$.</figcaption></figure>

**Remark 16.** Theorem 15 asserts that computing $\#(\vec{\mathcal{T}}, \mathcal{H})$ is FPT in the treewidth of $\vec{\mathcal{T}}$. In particular, for bounded-treewidth triangulations it can be computed in linear time. However, since tensor network contraction—the last part of the computation—is generally $\#\mathbf{P}$-hard [13], we expect this to hold for computing $\#(\vec{\mathcal{T}}, \mathcal{H})$ for general triangulations as well.

As motivation, let us recall the formula for the invariant $\#(\vec{\mathcal{D}}, \mathcal{H})$ from [28, Section 5]:

$$ \#(\vec{\mathcal{D}}, \mathcal{H}) := \mathcal{Z}(\vec{\mathcal{D}}, \mathcal{H}) \cdot \dim_{\mathbb{F}}(\mathcal{H})^{g(S)-|\alpha|-|\beta|}. \quad (2) $$

Here $g(S)$ is the genus of the surface $S$, and $|\alpha|$ and $|\beta|$ denote the number of $\alpha$- and $\beta$-curves of $\vec{\mathcal{D}}$, respectively. The “complicated” term $\mathcal{Z}(\vec{\mathcal{D}}, \mathcal{H}) \in \mathbb{F}$ is defined as the evaluation $\mathcal{Z}(\mathcal{K})$ of a specific tensor network $\mathcal{K}$ associated to $\vec{\mathcal{D}}$, built from (several copies of) the structure tensors of the Hopf algebra $\mathcal{H}$. We now very briefly and selectively review these notions.

**Hopf algebras and their structure tensors** A Hopf algebra $\mathcal{H}$ is a vector space $\mathbf{H}$ over a field $\mathbb{F}$ together with three $\mathbb{F}$-linear maps $\mathrm{M}: \mathbf{H} \otimes \mathbf{H} \to \mathbf{H}$ (multiplication), $\Delta: \mathbf{H} \to \mathbf{H} \otimes \mathbf{H}$ (comultiplication) and $\mathrm{S}: \mathbf{H} \to \mathbf{H}$ (antipode) satisfying certain axioms (cf. [28, Section 3]). We will assume that $\dim_{\mathbb{F}}(\mathbf{H}) < \infty$ and $\mathcal{H}$ is involutory, i.e., $\mathrm{S} \circ \mathrm{S} = \mathrm{id}_{\mathcal{H}}$. The maps $\mathrm{M}$, $\Delta$ and $\mathrm{S}$ can be regarded as tensors of type (1,2), (2,1) and (1,1), respectively, see Figure 11.

<figure><img src="image_18.png" /><figcaption>■ **Figure 11** The multiplication, comultiplication and antipode tensors of a Hopf algebra.</figcaption></figure>

**Example 17.** The group algebra $\mathcal{G} = \mathbb{F}G$ of a finite group $G$ is naturally a Hopf algebra: the multiplication is defined as $\mathrm{M}(g \otimes h) = gh$, the comultiplication as $\Delta(g) = g \otimes g$, and the antipode as $\mathrm{S}(g) = g^{-1}$. In [28, Sections 1 and 6] it is shown that $\#(\vec{\mathcal{D}}, \mathcal{G})$ equals the number of homomorphisms $\pi_1(\mathcal{M}) \to G$ from the fundamental group of the 3-manifold $\mathcal{M}$ described by $\vec{\mathcal{D}}$ to the group $G$. (In this case $\#(\vec{\mathcal{D}}, \mathcal{G})$ is independent of the chosen orientation for $\mathcal{D}$.)
## 5.1 Kuperberg's construction and the proof of Theorem 15

Following [28, Section 5], first we explain how the tensor network $\mathcal{K}$—whose evaluation $Z(\mathcal{K}) := Z(\tilde{\mathcal{D}}, \mathcal{H})$ appears in (2)—is constructed from an oriented Heegaard diagram $\tilde{\mathcal{D}}$. Then we prove Lemma 18, which—together with Theorem 19—implies Theorem 15.

**The construction of $\mathcal{K}$** As already mentioned, the building blocks of $\mathcal{K}$ are the structure tensors $M, \Delta$ and $S$ of the Hopf algebra $\mathcal{H}$ (Figure 11). The shorthands in Figure 12—which are justified by the fact that both abbeviated tensor networks, called the *tracial product* and *tracial coproduct* in [28], are cyclically symmetric$^{12}$—will be useful:

<figure><img src="image_19.png" /><figcaption>Figure 12 Diagrammatic abbreviations of the *tracial product* and *tracial coproduct* tensors.</figcaption></figure>

Let $\tilde{\mathcal{D}} = (\tilde{\mathcal{S}}, \tilde{\alpha}, \tilde{\beta})$ be an oriented Heegaard diagram. For every oriented $\alpha$-curve $\tilde{\alpha}_i \in \tilde{\alpha}$, we take a copy of the tracial product tensor $\begin{tikzpicture}[baseline={([yshift=-0.5ex]current bounding box.center)}] \node[circle, fill, inner sep=1pt] (A) at (0,0) {}; \node[circle, fill, inner sep=1pt] (B) at (1,0) {}; \draw[->] (A) -- (B); \node[above] at (0.5,0) {$c_1$}; \node[above] at (0.5,1) {$c_p$}; \end{tikzpicture}$, where the abstract indices $c_1, \dots, c_p$ correspond to the crossings on $\tilde{\alpha}_i$ (with the $\beta$-curves of $\tilde{\mathcal{D}}$) in the order they are encountered when traversing $\tilde{\alpha}_i$ following its orientation. We assign a copy $\begin{tikzpicture}[baseline={([yshift=-0.5ex]current bounding box.center)}] \node[circle, fill, inner sep=1pt] (A) at (0,0) {}; \node[circle, fill, inner sep=1pt] (B) at (1,0) {}; \draw[->] (A) -- (B); \node[above] at (0.5,0) {$c_1'$}; \node[above] at (0.5,1) {$c_q'$}; \end{tikzpicture}$ of the tracial coproduct tensor to each oriented $\beta$-curve $\tilde{\beta}_j \in \tilde{\beta}$ analogously. Note that each crossing $c$ between an $\alpha$- and a $\beta$-curve of $\tilde{\mathcal{D}}$ appears exactly twice as an abstract index of the above tensors: once at a product and once at a coproduct. The construction of $\mathcal{K}$ is concluded by contracting these indices (i.e., joining the respective arrows with *wires*) with a caveat: if the tangent vectors of the $\beta$- and $\alpha$-curves intersecting at $c$ form (in that order) a negatively oriented basis of the tangent space $T\tilde{\mathcal{S}}$, then the antipode tensor is interposed before contracting (Figure 13).

<figure><img src="image_20.png" /><figcaption>Figure 13 Instruction manual for assembling the tensor network $\mathcal{K}$ from its building blocks.</figcaption></figure>

A fully contracted tensor network $\mathcal{N}$ (such as $\mathcal{K}$) can be seen as a graph $(V(\mathcal{N}), E(\mathcal{N}))$ in the obvious way: $V(\mathcal{N})$ corresponds to the coupons of $\mathcal{N}$, whereas $E(\mathcal{N})$ to its wires.

**Lemma 18.** Let $\tilde{\mathcal{D}}$ be an oriented Heegaard diagram and $\mathcal{K}$ be the Kuperberg tensor network induced by $\tilde{\mathcal{D}}$. Then, the number of vertices and the treewidth of $\tilde{\mathcal{D}}$ and $\mathcal{K}$ satisfy

$$ |V(\mathcal{K})| \le 3|V(\tilde{\mathcal{D}})| \quad (3a) \qquad \text{and} \qquad \text{tw}(\mathcal{K}) \le 2\text{tw}(\tilde{\mathcal{D}}). \quad (3b) $$

**Proof.** Both inequalities (3a) and (3b) follow directly from the construction of $\mathcal{K}$. In fact, the local configurations shown in Figure 14 already reveal the close structural relationship between $\tilde{\mathcal{D}}$ and $\mathcal{K}$. We refer to Appendix E for the complete proof. ◀

**Proof of Theorem 15.** With Theorem 1 and Lemma 18 at hand, Theorem 15 is a consequence of the following general result about the computational cost of evaluating tensor networks.

<footnote>$^{12}$This is analogous to the fact that $\text{Tr}(A_1A_2\cdots A_n) = \text{Tr}(A_nA_1\cdots A_{n-1})$ for the trace of matrices.</footnote>
<figure><img src="image_21.png" /><figcaption>(a) Local picture of a Heegaard diagram $\mathcal{D}$ near an $\alpha$-curve $\alpha_1$</figcaption></figure>

<figure><img src="image_22.png" /><figcaption>(b) The corresponding local picture of the tensor network $\mathcal{K}$...</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>(c) ...and the local picture of its underlying simple graph $G_{\mathcal{K}}$</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>(d) Local picture of a Heegaard diagram $\mathcal{D}$ near an $\beta$-curve $\beta_1$</figcaption></figure>

<figure><img src="image_25.png" /><figcaption>(e) The corresponding local picture of the tensor network $\mathcal{K}$...</figcaption></figure>

<figure><img src="image_26.png" /><figcaption>(f) ...and the local picture of its underlying simple graph $G_{\mathcal{K}}$</figcaption></figure>

■ **Figure 14** The local structural correspondence between a Heegaard diagram $\mathcal{D}$ and the induced Kuperberg tensor network $\mathcal{K}$.

► **Theorem 19** ([40, Theorem 1], cf. [37, Theorem 4.6]). Any tensor network $\mathcal{N}$ with $n$ tensors can be evaluated in $O(2^{O(\mathrm{vc}(\mathcal{N}))}n)$ time, where $\mathrm{vc}(\mathcal{N})$ denotes the vertex congestion of $\mathcal{N}$.

Vertex congestion is a graph parameter similar to treewidth, discussed in [3, p. 135]. For a graph $G$ with maximum degree $\Delta$, we have $\mathrm{vc}(G) \le (3/2) \cdot \Delta \cdot (\mathrm{tw}(G) + 1)$, see [3, Theorem 1 and Remark 3]. Since Kuperberg’s tensor networks are 3-regular graphs, we have

► **Corollary 20.** Any Kuperberg tensor network $\mathcal{K}$ can be evaluated in time $O(2^{O(\mathrm{tw}(\mathcal{K}))}|\mathcal{K}|)$, where $\mathrm{tw}(\mathcal{K})$ denotes the treewidth and $|\mathcal{K}|$ the number of tensors of $\mathcal{K}$.

Now, if $\mathcal{K}$ is induced by an oriented triangulation $\mathcal{T}$ with $n$ tetrahedra, then $|\mathcal{K}| \le 3|V(\mathcal{D})|$ and $\mathrm{tw}(\mathcal{K}) \le 2\mathrm{tw}(\mathcal{D})$ by Lemma 18, and $|V(\mathcal{D})| \le 6$ and $\mathrm{tw}(\mathcal{D}) \le 12\mathrm{tw}(\mathcal{T})+11$ by Theorem 1. Combining these inequalities with Corollary 20, the Theorem 15 follows. ◀

References

1. A. Berezutskii, M. Liu, A. Acharya, et al. Tensor networks for quantum computing. *Nat. Rev. Phys.*, 7(10):581–593, 2025. doi:10.1038/s42254-025-00853-1.

2. J. Biamonte and V. Bergholm. Tensor networks in a nutshell, 2017. arXiv:1708.00006.

3. D. Bienstock. On embedding graphs in trees. *J. Comb. Theory, Ser. B*, 49(1):103–136, 1990. doi:10.1016/0095-8956(90)90066-9.

4. N. Brady, J. McCammond, and J. Meier. Bounding edge degrees in triangulated 3-manifolds. *Proc. Amer. Math. Soc.*, 132(1):291–298, 2004. doi:10.1090/S0002-9939-03-06981-8.

5. B. A. Burton. Computational topology with Regina: algorithms, heuristics and implementations. In *Geometry and Topology Down Under*, volume 597 of *Contemp. Math.*, pages 195–224. Am. Math. Soc., Providence, RI, 2013. doi:10.1090/comm/597/11877.

6. B. A. Burton. The HOMFLY-PT polynomial is fixed-parameter tractable. In *34th Int. Symp. Comput. Geom. (SoCG 2018)*, volume 99 of LIPIcs. Leibniz Int. Proc. Inform., pages 18:1–18:14. Schloss Dagstuhl–Leibniz-Zent. Inf., 2018. doi:10.4230/LIPIcs.SoCG.2018.18.
7 B. A. Burton, R. Budney, W. Pettersson, et al. Regina: Software for low-dimensional topology, 1999-2025. Version 7.4. URL: https://regina-normal.github.io.

8 B. A. Burton and R. G. Downey. Courcelle's theorem for triangulations. *J. Comb. Theory, Ser. A*, 146:264–294, 2017. doi:10.1016/j.jcta.2016.10.001.

9 B. A. Burton, T. Lewiner, J. Paixão, and J. Spreer. Parameterized complexity of discrete Morse theory. *ACM Trans. Math. Softw.*, 42(1):6:1–6:24, 2016. doi:10.1145/2738034.

10 B. A. Burton, C. Maria, and J. Spreer. Algorithms and complexity for Turaev–Viro invariants. *J. Appl. Comput. Topol.*, 2(1–2):33–53, 2018. doi:10.1007/s41468-018-0016-2.

11 B. A. Burton and W. Pettersson. Fixed parameter tractable algorithms in combinatorial topology. In *Proc. 20th Int. Conf. Comput. Comb. (COCOON 2014)*, volume 8591 of *Lect. Notes Comput. Sci.*, pages 300–311. Springer, 2014. doi:10.1007/978-3-319-08783-2_26.

12 B. A. Burton and J. Spreer. The complexity of detecting taut angle structures on triangulations. In *Proc. 24th Annu. ACM-SIAM Symp. Discrete Algorithms (SODA 2013)*, pages 168–183, 2013. doi:10.1137/1.9781611973105.13.

13 C. Damm, M. Holzer, and P. McKenzie. The complexity of tensor calculus. *Comput. Complexity*, 11(1-2):54–89, 2002. doi:10.1007/s00037-000-0170-4.

14 A. de Mesmay, J. Purcell, S. Schleimer, and E. Sedgwick. On the tree-width of knot diagrams. *J. Comput. Geom.*, 10(1):164–180, 2019. doi:10.20382/jocg.v10i1a6.

15 D. Eppstein. What is ... treewidth? *Notices Amer. Math. Soc.*, 72(2):172–175, 2025. URL: https://www.ams.org/journals/notices/202502/rnoti-p172.pdf.

16 F. Frick. *Combinatorial restrictions on cell complexes*. PhD thesis, TU Berlin, 2015. doi: 10.14279/depositonce-4545.

17 F. Gurski and R. Weishaupt. The behavior of tree-width and path-width under graph operations and graph transformations. *Algorithms*, 18(7):386, 2025. doi:10.3390/a18070386.

18 A. Hatcher. *Algebraic Topology*. Cambridge Univ. Press, Cambridge, 2002. URL: https://pi.math.cornell.edu/~hatcher/AT/ATpage.html.

19 A. He, J. Morgan, and E. K. Thompson. An algorithm to construct one-vertex triangulations of heegaard splittings. *J. Comput. Geom.*, 16(1):635–693, Nov. 2025. doi:10.20382/jocg.v16i1a18.

20 P. Heegaard. *Forstudier til en topologisk Teori for de algebraiske Fladers Sammenhæng* (in Danish). PhD thesis, Det Nordiske Forlag, 1898. URL: https://books.google.com/books?id=p9hMAAAAYAAJ. An English translation is available at https://webhomes.maths.ed.ac.uk/~v1ranick/papers/heegaardenglish.pdf.

21 P. Heegaard. Sur l'"Analysis situs". *Bull. Soc. Math. France*, 44:161–242, 1916. doi:10.24033/bsmf.968.

22 S. Hess. *Tensors for Physics*. Undergrad. Lect. Notes Phys. Springer, Cham, 2015. doi: 10.1007/978-3-319-12787-3.

23 K. Huszár. On the pathwidth of hyperbolic 3-manifolds. *Comput. Geom. Topol.*, 1(1):1–19, 2022. doi:10.57717/cgt.v1i1.4.

24 K. Huszár and J. Spreer. 3-Manifold triangulations with small treewidth. In *35th Int. Symp. Comput. Geom. (SoCG 2019)*, volume 129 of *LIPIcs. Leibniz Int. Proc. Inf.*, pages 44:1–44:20. Schloss Dagstuhl–Leibniz-Zent. Inf., 2019. doi:10.4230/LIPIcs.SoCG.2019.44.

25 K. Huszár and J. Spreer. On the width of complicated JSJ decompositions. *Discrete Comput. Geom.*, 2025. Advance online publication. doi:10.1007/s00454-025-00746-1.

26 K. Huszár, J. Spreer, and U. Wagner. On the treewidth of triangulated 3-manifolds. *J. Comput. Geom.*, 10(2):70–98, 2019. doi:10.20382/jogc.v10i2a5.

27 G. Kuperberg. Involutory hopf algebras and 3-manifold invariants, 1990. arXiv:math/9201301.

28 G. Kuperberg. Involutory Hopf algebras and 3-manifold invariants. *Internat. J. Math.*, 2(1):41–66, 1991. doi:10.1142/S0129167X91000053.

29 G. Kuperberg. Noninvolutory Hopf algebras and 3-manifold invariants. *Duke Math. J.*, 84(1):83–129, 1996. doi:10.1215/S0012-7094-96-08403-3.
30 M. Lackenby. Algorithms in 3-manifold theory. In I. Agol and D. Gabai, editors, *Surveys in 3-manifold topology and geometry*, volume 25 of *Surv. Differ. Geom.*, pages 163–213. Int. Press Boston, 2022. doi:10.4310/SDG.2020.v25.n1.a5.

31 C. Lunel and A. de Mesmay. A Structural Approach to Tree Decompositions of Knots and Spatial Graphs. In *39th Int. Symp. Comput. Geom. (SoCG 2023)*, volume 258 of *LIPIcs. Leibniz Int. Proc. Inf.*, pages 50:1–50:16. Schloss Dagstuhl–Leibniz-Zent. Inf., 2023. doi:10.4230/LIPIcs.SoCG.2023.50.

32 J. A. Makowsky. Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width. *Discrete Appl. Math.*, 145(2):276–290, 2005. doi:10.1016/j.dam.2004.01.016.

33 J. A. Makowsky and J. P. Mariño. The parametrized complexity of knot polynomials. *J. Comput. Syst. Sci.*, 67(4):742–756, 2003. Special issue on parameterized computation and complexity. doi:10.1016/S0022-0000(03)00080-1.

34 C. Maria. Parameterized complexity of quantum knot invariants. In *37th Int. Symp. Comput. Geom. (SoCG 2021)*, volume 189 of *LIPIcs. Leibniz Int. Proc. Inf.*, pages 53:1–53:15. Schloss Dagstuhl–Leibniz-Zent. Inf., 2021. doi:10.4230/LIPIcs.SoCG.2021.53.

35 C. Maria and J. Purcell. Treewidth, crushing and hyperbolic volume. *Algebr. Geom. Topol.*, 19(5):2625–2652, 2019. doi:10.2140/agt.2019.19.2625.

36 C. Maria and O. Rouillé. Computation of large asymptotics of 3-manifold quantum invariants. In *Proc. 23rd Symp. Algorithm Eng. Exp. (ALENEX 2021)*, pages 193–206. SIAM, 2021. doi:10.1137/1.9781611976472.15.

37 I. L. Markov and Y. Shi. Simulating quantum computation by contracting tensor networks. *SIAM J. Comput.*, 38(3):963–981, 2008. doi:10.1137/050644756.

38 S. Matveev. *Algorithmic Topology and Classification of 3-Manifolds*, volume 9 of *Algorithms Comput. Math*. Springer, Berlin, 2nd edition, 2007. doi:10.1007/978-3-540-45899-9.

39 E. E. Moise. Affine structures in 3-manifolds. V. The triangulation theorem and Hauptvermutung. *Ann. Math. (2)*, 56:96–114, 1952. doi:10.2307/1969769.

40 B. O’Gorman. Parameterization of tensor network contraction. In *14th Conf. Theory Quantum Comput. Commun. Cryptogr.*, volume 135 of *LIPIcs. Leibniz Int. Proc. Inform.*, pages 10:1–10:19. Schloss Dagstuhl. Leibniz-Zent. Inform., 2019. doi:10.4230/LIPIcs.TQC.2019.10.

41 T. Radó. Über den Begriff der Riemannschen Fläche. *Acta Sci. Math.*, 2(2):101–121, 1925.

42 N. Robertson and P. D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. *J. Algorithms*, 7(3):309–322, 1986. doi:10.1016/0196-6774(86)90023-4.

43 J. H. Rubinstein, H. Segerman, and S. Tillmann. Traversing three-manifold triangulations and spines. *Enseign. Math.*, 65(1-2):155–206, 2019. doi:10.4171/lem/65-1/2-5.

44 M. Scharlemann. Heegaard splittings of compact 3-manifolds. In *Handbook of Geometric Topology*, pages 921–953. North-Holland, 2001. doi:10.1016/B978-044482432-5/50019-6.

45 J. Schultens. *Introduction to 3-Manifolds*, volume 151 of *Grad. Stud. Math. Am. Math. Soc.*, Providence, RI, 2014. doi:10.1090/gsm/151.

**A On edge valence, experimentally**

The treewidth of a triangulation is an indicator of *global sparsity*. While it measures how tree-like the gluing relation between tetrahedra is, it does not capture finer information about their proximity. Indeed, *tree decompositions* of triangulations relate only those tetrahedra glued along a common facet, and are blind to tetrahedra that are adjacent merely along an edge. The *valence* of an edge in a triangulation is the number of times it appears as an edge of some tetrahedron (counted with multiplicities). Although the average edge valence in a triangulated closed 3-manifold is bounded, the valence may vary widely among edges; in particular, a single edge may be incident to all tetrahedra. In this sense, edge valence serves as an indicator of *local sparsity*.
In practice, high edge valences may significantly slow down computations. Many fundamental procedures—based on normal surfaces (e.g., sphere recognition), hyperbolic geometry (e.g., Thurston’s gluing equations), or colorings (e.g., quantum invariants)—involve systems of equations that become increasingly interdependent as edge valences vary widely. To illustrate the practical consequences of this phenomenon, Figures 15 and 16 show the number of admissible colorings for the Turaev–Viro quantum invariant at $U_q(\mathrm{sl}_2(\mathbb{C}))$ as a function of the variance of edge valences in triangulations of the lens space $L(11, 1)$ and the Poincaré sphere. Since the number of admissible colorings directly affects the running time of backtracking algorithms for computing Turaev–Viro invariants [36], this provides concrete evidence of the computational impact of edge-valence variability.

We also present the distribution of edge-valence variances among reduced triangulations of these two manifolds, which represent realistic algorithmic inputs. All triangulations were generated with Regina [7, 5], and the reduced triangulations are local minima of Regina’s simplification heuristics.

<figure><img src="image_27.png" /><figcaption>**Figure 15** Left: the number of admissible colorings for the Turaev–Viro quantum invariant $\mathrm{TV}_{11,1}(\mathrm{sl}_2(\mathbb{C}))$ for 10 000, size 12, non-simplified triangulations of the lens space $L(11, 1)$, as a function of the variance of edge valence. Right: 100 heuristically simplified triangulations of $L(11, 1)$, size 8 to 13, plotted against the variance of their edge valence.</figcaption></figure>

<figure><img src="image_28.png" /><figcaption>**Figure 16** Left: the number of admissible colorings for the Turaev–Viro quantum invariant $\mathrm{TV}_{11,1}(\mathrm{sl}_2(\mathbb{C}))$ for 10 000, size 13, non-simplified triangulations of the Poincaré sphere, as a function of the variance of edge valence. Right: 43 heuristically simplified triangulations of the Poincaré sphere, size 5 to 11, plotted against the variance of their edge valence.</figcaption></figure>
B Completion of the proof of Claim 11

Here we provide the omitted details of the proof of Claim 11 from Section 4. In particular
we give the complete case analysis for verifying the “edge coverage” property of the tree
decomposition $\mathcal{X}'$ of the triangulation $\mathcal{T}^*$ defined in Lemma 10.

**Proof of Edge coverage in Claim 11.** There are several types of tetrahedra that are adjacent in $\mathcal{T}^*$. Let $a$ and $b$ be distinct vertices of $\mathcal{T}(0)$ appearing as vertices of $\mathcal{T}^*$. Let $\sigma_1$ and $\sigma_2$ be adjacent tetrahedra of $\mathcal{T}^*$; we have, considering indices of the $u_i$ are taken modulo $k$, and indices of the $v_\ell$ are taken modulo $m$: all following configurations are illustrated in Figure 9.

(a) If $\sigma_1$ and $\sigma_2$ are adjacent through a triangular face $\{x, y, z\}$ contained in a 2-face $F$, i.e.,
$\sigma_1 = \{x, y, z, a\}$ and $\sigma_2 = \{x, y, z, b\}$, with $x, y, z \in \{u_i, v_j, w\}_{i,j}$, then $\sigma_1$ and $\sigma_2$ appear
in a same bag $B'_\tau$, regardless of the type of triangle $\{x, y, z\}$.

(b) If $\sigma_1$ and $\sigma_2$ are adjacent through a triangle $\{a, v_\ell, u_i\}$ with $\sigma_1 = \{a, v_\ell, u_{i-1}, u_i\}$ and $\sigma_2 = \{a, v_\ell, u_i, u_{i+1}\} - u_{i-1}$ and $u_i$ are adjacent in $\Gamma(\mathcal{T})$ and must appear in a same bag $B_\tau$ of $\mathcal{X}$. By 1, both $\sigma_1$ and $\sigma_2$ appear in $B'_\tau$ of $\mathcal{X}'$.

(c) If $\sigma_1$ and $\sigma_2$ are adjacent through a triangle $\{a, v_{\ell-1}, u_{\ell(d-1)}\}$ with $\sigma_1 = \{a, v_{\ell-1}, u_{\ell(d-1)-1}, u_{\ell(d-1)}\}$ and $\sigma_2 = \{a, v_{\ell-1}, u_{\ell(d-1)}, v_\ell\} - u_{\ell(d-1)-1}$ and $u_{\ell(d-1)}$ are adjacent in $\Gamma(\mathcal{T})$ and must appear in a same bag $B_\tau$ of $\mathcal{X}$. By 1 for $\sigma_1$, and 2 for $\sigma_2$, both $\sigma_1$ and $\sigma_2$ appear in $B'_\tau$ of $\mathcal{X}'$. The case $\sigma_1 = \{a, v_{m-1}, u_{k-1}, u_0\}$ and $\sigma_2 = \{a, v_{m-1}, u_0, v_0\}$ works similarly.

(d) If $\sigma_1$ and $\sigma_2$ are adjacent through a triangle $\{a, v_\ell, u_{\ell(d-1)}\}$ with $\sigma_1 = \{a, v_{\ell-1}, u_{\ell(d-1)}, v_\ell\}$ and $\sigma_2 = \{a, v_\ell, u_{\ell(d-1)}, u_{\ell(d-1)+1}\}$ — By 2 for $\sigma_1$ and 1 for $\sigma_2$, they both appear in any bag $B'_\tau$ such that $B_\tau$ contains $u_{\ell(d-1)}$.

(e) If $\sigma_1$ and $\sigma_2$ are adjacent through a triangle $\{a, v_{\ell-1}, v_\ell\}$ with $\sigma_1 = \{a, w, v_{\ell-1}, v_\ell\}$ and $\sigma_2 = \{a, v_{\ell-1}, u_{\ell(d-1)}, v_\ell\}$ — By 3 for $\sigma_1$ and 2 for $\sigma_2$, they both appear in any bag $B'_\tau$ such that $B_\tau$ contains $u_{\ell(d-1)}$.

(f) If $\sigma_1$ and $\sigma_2$ are adjacent through a triangle $\{a, w, v_\ell\}$ with $\sigma_1 = \{a, w, v_{\ell-1}, v_\ell\}$ and $\sigma_2 = \{a, w, v_\ell, v_{\ell+1}\} - u_{(\ell+1)(d-1)-1}$ and $u_{(\ell+1)(d-1)}$ are adjacent in $\Gamma(\mathcal{T})$ and must appear in a same bag $B_\tau$ of $\mathcal{X}$. By 3, both $\sigma_1$ and $\sigma_2$ appear in $B'_\tau$ of $\mathcal{X}'$.

(g) If $\sigma_1$ and $\sigma_2$ are adjacent through a triangle $\{a, u_i, u_{i+1}\}$ with $\sigma_1 = \{a, v_\ell, u_i, u_{i+1}\}$ and $\sigma_2 = \{a, v'_j, u_{i+1}, u_i\}$, where $v_\ell$ and $v'_j$ are inner vertices of distinct 2-faces $F_1$ and $F_2$. By 1, either $\sigma_1$ and $\sigma_2$ both appear in any bag $B'_\tau$ such that $B_\tau$ contains $u_i$ (if the orientations of the 2-faces are incompatible at the edge $\{u_i, u_{i+1}\}$) or $\sigma_1$ appears in the bags $B'_\tau$ such that $B_\tau$ contains $u_i$ and $\sigma_2$ appears in the bags $B'_\tau$ such that $B_\tau$ contains $u_{i+1}$. However, for the latter, $u_i$ and $u_{i+1}$ are adjacent in $\Gamma(\mathcal{T})$ and there must be a bag $B_\tau$ containing both $u_i$ and $u_{i+1}$ in $\mathcal{X}$; in consequence $\sigma_1, \sigma_2 \in B'_\tau$ in $\mathcal{X}$. $\quad$
C Some useful lemmas for Section 4

C.1 Iterated radicals, limit and speed of convergence

► **Lemma 21** (Iterated radicals). Let $c$ be a positive constant, and let $L = c + \frac{1}{2} + \sqrt{c + \frac{1}{4}} > 0$. Consider the sequence $a_0 > L$, $a_{n+1} = \sqrt{a_n} + c$. Then $(a_n)_{n \ge 0}$ is a decreasing sequence converging to $L$. Additionally, for every $n \in \mathbb{N}$ we have the bound:

$$0 \le a_n \le a_0^{1/2^n} + L.$$

In particular, for $c = 4$, this gives $L < 6.32$.

**Proof.** The quantity $L$ is computed as a solution to the equation $x = \sqrt{x} + c$, obtained by studying the degree two polynomial $L = (L - c)^2$. We prove the bound by induction. The property holds for $a_0$. Suppose $a_n \le a_0^{1/2^n} + L$, we have:

$$ \begin{aligned} a_{n+1} = \sqrt{a_n} + c &\le \sqrt{(a_0^{1/2^n} + L)} + c \quad \text{(by induction)} \\ &\le a_0^{1/2^{n+1}} + \sqrt{L} + c \quad \text{(by concavity of } \sqrt{\cdot}\text{)} \\ &= a_0^{1/2^{n+1}} + L. \quad \text{(by using } L = \sqrt{L} + c) \quad \blacksquare \end{aligned} $$

Next, we evaluate how fast $a_n$ converges within a small neighborhood of its limit.

► **Lemma 22.** For $n \ge \log_2 \log_2 x$, $|a_n - \lim_{n \to \infty} a_n| \le 2$.

**Proof.** We compute $n$ such that $a_n \le a_0^{1/2^n} + L \le L + 2$. Under the hypothesis,

$$a_0^{1/2^n} \le 2 \iff 2^{\frac{\log_2 a_0}{2^n}} \le 2 \iff \frac{\log_2 a_0}{2^n} \le 1 \iff \log_2 a_0 \le 2^n \iff \log_2 \log_2 a_0 \le n. \blacksquare$$

► **Lemma 23.** Consider the sequences $x_n, y_n$ such that $x_0, y_0 > 0$ and $x_{n+1} = (28+4\sqrt{6})x_n + (16+4\sqrt{6})y_n$ and $y_{n+1} = (6+\sqrt{6})(x_n + y_n)$. Then, setting $\lambda = 30+4\sqrt{6}$ gives,

$$x_n < c_1 \lambda^n (x_0 + y_0) + o(\lambda^n) \quad \text{and} \quad y_n < c_2 \lambda^n (x_0 + y_0) + o(\lambda^n),$$

for $c_1, c_2 > 0$ constants.

**Proof.** Consider

$$\begin{pmatrix} x_n \\ y_n \end{pmatrix} = A^n \begin{pmatrix} x_0 \\ y_0 \end{pmatrix}, \quad \text{with} \quad A = \begin{pmatrix} 28+4\sqrt{6} & 16+4\sqrt{6} \\ 6+\sqrt{6} & 6+\sqrt{6} \end{pmatrix}.$$

Diagonalizing $A$, that is, writing $A = PDP^{-1}$ with:

$$P = \begin{pmatrix} 8+\sqrt{6} & 2 \\ 1 & -(6+\sqrt{6}) \end{pmatrix}, P^{-1} = \frac{1}{62+20\sqrt{6}} \begin{pmatrix} 6+\sqrt{6} & 2 \\ 1 & -(8+2\sqrt{6}) \end{pmatrix}, \\ \text{and } D = \begin{pmatrix} 30+4\sqrt{6} & 0 \\ 0 & 4+\sqrt{6} \end{pmatrix},$$

we deduce the desired result by applying $A^n = P^{-1}D^n P$ to $(x_0, y_0)^T$.

◀
## C.2 Counting edge valences in triangulated 3-manifolds

**Lemma 24** (Euler characteristic argument). In any triangulation $\mathcal{T}$ of a closed 3-manifold $\mathcal{M}$ with $v$ vertices, $e$ edges, $f$ faces, and $n$ tetrahedra, we have $e = v + n$.

*Proof.* As $\mathcal{M}$ is closed, every face of $\mathcal{T}$ is shared by exactly two tetrahedra, thus $f = 2n$. Every odd-dimensional closed manifold has Euler characteristic zero, see, e.g. [18, Corollary 3.37], hence $v - e + f - n = 0$. We conclude $e = n + v$. ◀

**Corollary 25** (Sum of edge valences). In any triangulation $\mathcal{T}$ of a closed 3-manifold $\mathcal{M}$ with $n$ tetrahedra, the sum $\mathcal{G} = \sum_{e \in \mathcal{T}(1)} \mathrm{val}(e)$ of edge valences equals $6n$.

*Proof.* The sum $\mathcal{G}$ counts, with multiplicity, the incidences between edges and faces. Since every face is triangular, it follows that $\mathcal{G} = 3 \cdot |\mathcal{T}(2)|$. By Lemma 24 we obtain $\mathcal{G} = 6n$. ◀

**Lemma 26** (Sum of square roots of edge valences). In any triangulation $\mathcal{T}$ of a closed 3-manifold $\mathcal{M}$ with $v$ vertices and $n$ tetrahedra, we have $\sum_{e \in \mathcal{T}(1)} \sqrt{\mathrm{val}(e)} \le \sqrt{6}(n + v)$.

*Proof.* By the Cauchy–Schwarz inequality, any positive real numbers $a_1, \dots, a_n$ satisfy $\sqrt{a_1} + \dots \sqrt{a_n} \le \sqrt{n}\sqrt{a_1 + \dots a_n}$. Applying this to the edge valences we get

$$ \sum_{e \in \mathcal{T}(1)} \sqrt{\mathrm{val}(e)} \stackrel{\text{Cauchy-Schwarz}}{\le} \sqrt{|\mathcal{T}(1)|} \sqrt{\sum_{e \in \mathcal{T}(1)} \mathrm{val}(e)} \stackrel{\text{Lem. 24, Cor. 25}}{\le} \sqrt{n+v\sqrt{6n}} \le \sqrt{6}(n+v). $$

◀

# D Very briefly on tensor networks

Originating in physics [22, Section 1.3], tensors generalize vectors and linear transformations to a multilinear setting. Tensor networks play an important role in quantum computing [1]. We refer to [28, Section 2] for a tailored introduction and to [2] for more details.

**Tensors** Let $V$ be a finite-dimensional vector space over a field $\mathbb{F}$. A tensor $T$ is an element of some tensor product space $V_1 \otimes \dots \otimes V_r$, where $V_i = V$ or $V_i = V^*$ for each $i$. If $p$ is the number of $V$-factors in this product, then we say $T$ is of type $(p, r-p)$. We let $T_q^p(V)$ denote the set of tensors of type $(p, q)$.

**Example 27.** Tensors of type $(0, 0)$, $(1, 0)$, $(0, 1)$, $(1, 1)$, and $(0, 2)$ correspond to scalars, vectors, linear functionals, linear transformations, and bilinear forms, respectively. An example for a $(1, 2)$-tensor is the cross product $(v, w) \mapsto v \times w$ of two vectors in $\mathbb{R}^3$.

Two tensor operations are essential here. First, given two tensors, $T$ of type $(p, q)$ and $U$ of type $(r, s)$, their tensor product $T \otimes U$ is a tensor of type $(p+r, q+s)$. Second, if $p, q > 0$, then for any $i \in \{1, \dots, p\}$ and $j \in \{1, \dots, q\}$ the $(i, j)$-contraction map $C_{i,j}: T_q^p(V) \to T_{q-1}^{p-1}(V)$ is defined by applying the canonical map $V \otimes V^* \to \mathbb{F}$, $v \otimes f \mapsto f(v)$ to the $i^{\text{th}}$ $V$-factor and the $j^{\text{th}}$ $V^*$-factor. E.g., if $A \in T_1^1(V)$ then $C_{1,1}(A) = \mathrm{Tr}(A)$ is just the trace of $A$.

**Index notation** The (abstract) index notation provides a succinct way to describe basis-independent computations with tensors. In this notation, for example, a tensor $T \in V \otimes V \otimes V^* \otimes V \otimes V^*$ is written as $T^{a_1 a_2}_{a_3} {}^{a_4}_{a_5}$, where $a_i$ is an upper (resp. lower) index if $V_i = V$ (resp. $V_i = V^*$). These abstract indices $a_i$ are pairwise different symbols that merely indicate the slots of $T$—they are not numerical indices. The tensor product of two tensors, say $T^{a}_{bc}$ and
$U^d_e$, is written by juxtaposition: $T^{a}_{bc}U^d_e$. Performing an $(i, j)$-contraction is indicated by setting the $i^{th}$ upper index and the $j^{th}$ lower index to be equal, e.g., $C_{1,2}(T^{a}_{bc}U^d_e) = T^{a}_{ba}U^d_e$, or $C_{2,1}(T^{a}_{bc}U^d_e) = T^{a}_{bc}U^b_e$. Tensor products and contractions encompass many standard operations in linear algebra, e.g., $A^{a}_{b}v^b$ equals the A-image of the vector $v$ (cf. Figure 18).<fnref n="13" />

**Tensor diagrams** Importantly, the index notation can be developed into a diagrammatic notation. To construct the diagram of a tensor $T$ given by index notation, first take a coupon $\bar{T}$. Then, going around $\bar{T}$ in counter-clockwise direction, for each index $a_i$ attach to $\bar{T}$ an outgoing (resp. incoming) $a_i$-labeled arrow, whenever $a_i$ is an upper (resp. lower) index. The diagram of $T \otimes U$ is the disjoint union of the diagrams of $T$ and $U$, and a contraction of an upper-lower index pair is indicated by joining the respective arrows with a wire and erasing the common label from the drawing, cf. Figures 18 and 19. Repeatedly performing these operations gives rise to what we call a tensor network. If a tensor network $\mathcal{N}$ has no labeled arrows—because each arrow is incident to two coupons (which may coincide)—then $\mathcal{N}$ is fully contracted. In this case $\mathcal{N}$ represents a scalar $\mathcal{Z}(\mathcal{N}) \in \mathbb{F}$, which we call the evaluation<fnref n="14" /> of $\mathcal{N}$.

<figure><img src="image_29.png" /><figcaption>■ **Figure 17** Representing tensors using the index notation (bottom) and via diagrams (top).</figcaption></figure>

<figure><img src="image_30.png" /><figcaption>■ **Figure 18** Many basic operations in linear algebra can be represented by small tensor networks.</figcaption></figure>

<figure><img src="image_31.png" /><figcaption>■ **Figure 19** Tensor operations in index notation (bottom) and via tensor networks (top).</figcaption></figure>

<footnote n="13">¹³Moreover, using the *Einstein summation convention*, i.e., summing over the indices appearing twice, $A^{a}_{b}v^{b} = A(v)^{a}$ exactly describes how to calculate the coordinates of $A(v)$, once a basis for $V$ is fixed.</footnote>

<footnote n="14">¹⁴The word *contraction* is also commonly used to denote the evaluation of a tensor network.</footnote>
**E The complete proof of Lemma 18**

**Proof of Lemma 18.** As stated in Section 5.1, both inequalities (3a) and (3b) follow directly from the construction of $\mathcal{K}$.

To show (3a), note that $|V(\mathcal{K})| = \#(\mathcal{M}) + \#(\mathcal{\Delta}) + \#(\mathcal{S})$, where $\#(\mathcal{M})$, $\#(\mathcal{\Delta})$ and $\#(\mathcal{S})$ count the multiplication, comultiplication and antipode tensors comprising $\mathcal{K}$. Inspecting Figure 12, we see that the number of labeled arrows of the tracial (co)product tensor equals the number of its constituent (co)multiplication tensors. Now, in the construction of $\mathcal{K}$ the labels correspond to the vertices (i.e., crossings) of $\tilde{\mathcal{D}}$. As each label appears once at an $(\mathcal{M})$-coupon and once at a $(\mathcal{\Delta})$-coupon, we obtain $\#(\mathcal{M}) + \#(\mathcal{\Delta}) = 2|V(\tilde{\mathcal{D}})|$. The inequality $\#(\mathcal{S}) \le |V(\tilde{\mathcal{D}})|$ is immediate, since $V(\tilde{\mathcal{D}})$ corresponds to all crossings, while the $(\mathcal{S})$-coupons to the negative crossings of $\tilde{\mathcal{D}}$.

To show (3b), first note that treewidth is invariant under subdividing edges (see, e.g., [17, Section 3.6]) thus the presence of antipode tensors does not affect the treewidth of $\mathcal{K}$. Hence, we may assume that $\mathcal{K}$ does not contain any antipode tensors. As for $\mathcal{M}(\mathcal{D})$ and $\mathcal{\Delta}(\mathcal{D})$, the presence of these tensors in $\mathcal{K}$ correspond to degree-one vertices in its underlying simple graph $G_{\mathcal{K}}$, see Figures 14c and 14f. Since treewidth is not sensitive to loops or multiple edges either, we get that $\mathrm{tw}(G_{\mathcal{K}}) = \mathrm{tw}(\mathcal{K})$. Let $G_{\mathcal{K}}^*$ be the subgraph of $G_{\mathcal{K}}$ obtained by erasing all such degree-one vertices in $G_{\mathcal{K}}$. Note that $\mathrm{tw}(G_{\mathcal{K}}^*) = \mathrm{tw}(G_{\mathcal{K}})$, since attaching degree-one vertices to a graph does not change its treewidth. Hence we are left with bounding $\mathrm{tw}(G_{\mathcal{K}}^*)$.

Let $\mathcal{X}_{\tilde{\mathcal{D}}} = (T, \mathcal{B})$ be an optimal tree decomposition of $\tilde{\mathcal{D}}$, and let $V(\tilde{\mathcal{D}}) = \{c_1, \dots, c_m\}$. By construction of $\mathcal{K}$, each vertex of $G_{\mathcal{K}}^*$ is incident to precisely one $c_i$-labeled edge and those labels are unique. We define the desired tree decomposition $\mathcal{X}' = (T', \mathcal{B}')$ of $G_{\mathcal{K}}^*$ as follows:

- $T' := T = (I, F)$, i.e., the tree structure of the decomposition is the same as for $\mathcal{X}_{\tilde{\mathcal{D}}}$.

- $\mathcal{B}' := \{B'_i : i \in I\}$ and for each $i \in I$ we obtain $B'_i$ by first taking $B_i \in \mathcal{B}$, then replacing each vertex $c \in B_i$ with the two vertices of $G_{\mathcal{K}}^*$ that are connected by the $c$-labeled edge.

Clearly, $|B'_i| = 2|B_i|$ for each $i \in I$. To see that $\mathcal{X}' = (T', \mathcal{B}')$ is a valid tree decomposition of $G_{\mathcal{K}}^*$, note the following: 
1. Every vertex $v \in V(G_{\mathcal{K}}^*)$ is contained by some bag of $\mathcal{B}'$, since $v$ is incident to at least one labeled edge. 
2. For every edge $e = \{u, v\} \in E(G_{\mathcal{K}}^*)$, if $e$ is labeled, then $u$ and $v$ are readily contained in some common bag of $\mathcal{B}'$. If $e$ is not labeled, then let $c_u$ and $c_v$ be the labels of the labeled edges incident to $u$ and $v$, respectively. Note that $c_u$ and $c_v$ are successive crossings along some $\alpha$- or $\beta$-curve of $\tilde{\mathcal{D}}$. Hence by the edge coverage property of $\mathcal{X}_{\tilde{\mathcal{D}}}$ there is a bag $B_i \in \mathcal{B}$ that contains both $c_u$ and $c_v$. But then $B'_i$ contains, by definition, both $u$ and $v$. 
3. By construction of $\mathcal{X}'$, the subtree property is automatic. 

$\quad$