On Sparse Representations of 3-Manifolds

Any triangulation $𝒯$ of a 3-manifold $ℳ$ induces a canonical handle decomposition $\mathrm{chd}(𝒯)$ of $ℳ$, in which the $k$-handles (all 3-balls) correspond to the $(3-k)$-simplices of $𝒯$. Informally, $\mathrm{chd}(𝒯)$ is the “thickening” of $𝒯$ (see Figure 4). For each tetrahedron $\sigma \in 𝒯(3)$, take a 0-handle centered at its barycenter. For each triangle $t\in 𝒯(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 𝒯(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 𝒯(0)$, attach a 3-handle along a 2-sphere to fill the void surrounding $v$.

The union ${\mathscr{H}}_1$ of the 0- and 1-handles and the union ${\mathscr{H}}_2$ of the 2- and 3-handles of $\mathrm{chd}(𝒯)$ are both handlebodies that together form a Heegaard splitting of the 3-manifold triangulated by $𝒯$. Letting $𝒮:={\mathscr{H}}_1\cap {\mathscr{H}}_2$ and taking the meridional curves of the 2-handles and those of the 1-handles as $\alpha$- and $\beta$-curves, respectively (Figure 4), we obtain the Heegaard diagram $𝒟(𝒯)=(𝒮,𝜶,𝜷)$, where $𝜶=\{{\alpha }_e:e\in 𝒯(1)\}$ and $𝜷=\{{\beta }_t:t\in 𝒯(2)\}$. We call $𝒟(𝒯)$ the Heegaard diagram induced by the triangulation $𝒯$.

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

• $\mathbf{■}$

  $T^{\prime }=T$, i.e., the tree structure of the decomposition remains the same.

• $\mathbf{■}$

  ${ℬ}^{\prime }=\{B_i^{\prime }:i\in I\}$ and for each $i\in I$, the bag $B_i^{\prime }$ is obtained from $B_i$ by replacing each $\sigma \in B_i$ with the (at most) 12 vertices of $𝒟$ incident to $\sigma$, see Figure 4.

Clearly, $|B_i^{\prime }|\le 12|B_i|$. We now check that ${𝒳}^{\prime }=(T^{\prime },{ℬ}^{\prime })$ is a tree decomposition of $𝒟$.

Vertex coverage.

Consider a vertex $v\in V(𝒟)$. By construction, there exists a tetrahedron $\sigma \in 𝒯$, such that $v$ is incident to $\sigma$. Thus, for any $i\in I$, $v\in B_i^{\prime }\iff \sigma \in B_i$. However, since ${\bigcup }_{i\in I}{B}_i=V(\mathrm{\Gamma }(𝒯))$, this implies ${\bigcup }_{i\in I}{B}_i^{\prime }=V(𝒟)$ as well.

Edge coverage.

Let $e=\{u,v\}\in E(𝒟)$ be any arc of the diagram. Again, by construction of $𝒟$, there exists a tetrahedron $\sigma \in 𝒯$ that entirely contains $e$. Let $B_i$ be a bag that contains $\sigma$. Then $B_i^{\prime }$ must contain both $u$ and $v$.

Subtree property.

Fix a vertex $v\in V(𝒟)$ and consider $I_v^{\prime }:=\{i\in I:v\in B_i^{\prime }\}$. We need to show that $I_v^{\prime }$ spans a connected subtree of $T^{\prime }=T$. Let $\sigma ,\tau \in 𝒯$ 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 ${ℬ}^{\prime }$ it follows that $I_v^{\prime }=I_{\sigma }\cup I_{\tau }$. Since $𝒳$ is a tree decomposition of $\mathrm{\Gamma }(𝒯)$, each of $I_{\sigma }$ and $I_{\tau }$ spans a connected subtree in $T^{\prime }$. Moreover, $I_{\sigma }\cap I_{\tau }\ne \mathrm{\varnothing }$: either $\sigma =\tau$, or $\{\sigma ,\tau \}\in E(\mathrm{\Gamma }(𝒯))$, 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^{\prime }$ spans a connected subtree as well.

$◀$

We briefly comment on the computational cost of extracting the Heegaard diagram $𝒟(𝒯)$ from a given triangulation $𝒯$ with $n$ tetrahedra. Recall that for an abstract simplicial complex $𝒞$, its barycentric subdivision ${𝒞}^{\prime }$ is the simplicial complex whose ground set is $𝒞$, and a collection $\{{\tau }_0,\mathrm{\dots },{\tau }_k\}$ forms a $k$-simplex in ${𝒞}^{\prime }$ precisely when the simplices ${\tau }_i\in 𝒞$ are nested, that is, when ${\tau }_0\subset \mathrm{\cdots }\subset {\tau }_k$. Although a triangulation $𝒯$ 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 ${𝒯}^{\prime \prime }$ naturally contains both the canonical handle decomposition $\mathrm{chd}(𝒯)$ and the induced Heegaard diagram $𝒟(𝒯)$. As the barycentric subdivision of a tetrahedron contains 24 tetrahedra, $|{𝒯}^{\prime \prime }|={24}^2|𝒯|=576|𝒯|$.

Every vertex $v$ of ${𝒯}^{\prime }$ is of the form $v=\{\tau \}$ for some simplex $\tau \in 𝒯$. Let $\iota :{𝒯}^{\prime }(0)\hookrightarrow {𝒯}^{\prime \prime }(0)$ be the natural inclusion defined by $\iota (\{\tau \})=\{\{\tau \}\}$. For every $w\in \mathrm{im}(\iota )$, let $h_w$ be the smallest subcomplex of ${𝒯}^{\prime \prime }$ containing all $3$-faces incident to $w$. If $w$ corresponds to a simplex $\sigma \in 𝒯$ of dimension $3-k$, then $h_w$ is regarded as a $k$-handle. The collection $\{h_w:w\in \mathrm{im}(\iota )\}$ forms the canonical handle decomposition $\mathrm{chd}(𝒯)$. See Figure 5.

To extract the induced Heegaard diagram $𝒟(𝒯)$ from ${𝒯}^{\prime \prime }$, we need to pinpoint its $\alpha$- and $\beta$-curves, as well as the splitting surface $𝒮$ in ${𝒯}^{\prime \prime }$. We illustrate this via concrete examples; see Figure 6. We start with the $\alpha$-curves. Let $e\in 𝒯(1)$ be an edge of $𝒯$, and assume that $e$ is contained in four distinct tetrahedra ${\sigma }_1,{\sigma }_2.{\sigma }_3,{\sigma }_4$ of $𝒯$. Let $t_{ij}$ denote the triangular face shared by ${\sigma }_i$ and ${\sigma }_j$. Consider the subcomplex $C_e$ of ${𝒯}^{\prime }$ 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 ${𝒯}^{\prime \prime }$ (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^{\prime }$ adjacent to $\{\{e\}\}$ (Figure 6, top right). The $\beta$-curves can be located analogously (Figure 6, bottom row).

A triangulation of the splitting surface $𝒮$ can also be readily obtained as the boundary of the subcomplex of ${𝒯}^{\prime \prime }$ formed by the union of the triangulated 2- and 3-handles of $\mathrm{chd}(𝒯)$. Using standard data structures to represent these objects (such as in Regina [4]), all of these operations can be performed in linear time in terms of $n=|𝒯|$.

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

Note that, given the spine $S$, we can recover $ℳ$ 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 $𝒯$). 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 [13, 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.

Consider a $2$-face $F:=F_e$ of the spine $S$ transverse to an edge $e\in 𝒯(1)$. This face $F$ is a $k$-gon, where $k=\mathrm{val}(e)$, whose vertices are the centers of the tetrahedra of $𝒯$ 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 $u_0,\mathrm{\dots },u_{k-1}$ in accordance with this orientation. Introduce a ring of $m$ interior vertices $v_0,\mathrm{\dots },v_{m-1}$, and connect each $v_i$ to $v_{i-1}$ and $v_{i+1}$ (indices $modm$). For each , connect $v_i$ to the boundary vertices $u_{i(d-1)},\mathrm{\dots },u_{(i+1)(d-1)}$. The final interior vertex $v_{m-1}$ is connected to $u_{(m-1)(d-1)},\mathrm{\dots },u_{k-1},u_0$. The inequalities ensure that the vertices $u_i$ and $v_{\mathrm{\ell }}$, 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.

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

We proceed with investigating the maximum edge valence and the treewidth of ${𝒯}^{\ast }$.

We consider, case by case, the different types of edges in ${𝒯}^{\ast }$. Let $a$ denote a vertex of $𝒯(0)$, and let $u_i$, $v_{\mathrm{\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., $\mathrm{val}(\{a,w\})=m$.

Type $\{a,v_{\mathrm{\ell }}\}$.

The valence of the edge of this type is equal to the degree of $v_{\mathrm{\ell }}$ 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 $\mathrm{val}(\{a,u_i\})\le 9$.

Type $\{w,v_{\mathrm{\ell }}\}$ or $\{v_{\mathrm{\ell }},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_{\mathrm{\ell }},u_i,u_{i+1}\}$ per 2-face that contains it, and is contained in at most three 2-faces, therefore $\mathrm{val}(\{u_i,u_{i+1}\})\le 3$.

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

Consider a tree decomposition $𝒳=(T,ℬ)$ of the graph $\mathrm{\Gamma }(𝒯)$ with optimal width $\mathrm{𝐭𝐰}$.

By construction, every tetrahedron of ${𝒯}^{\ast }$ contains a vertex of $𝒯(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_{\mathrm{\ell }},u_{i-1},u_i\}$, $\{v_{\mathrm{\ell }-1},u_{\mathrm{\ell }(d-1)},v_{\mathrm{\ell }+1}\}$, or $\{w,v_{\mathrm{\ell }-1},v_{\mathrm{\ell }}\}$. For any 2-face of $S$, the boundary vertices $u_0,\mathrm{\dots },u_{k-1}$ correspond to nodes of the graph $\mathrm{\Gamma }(𝒯)$, and consequently each of them appears in some bag of this tree decomposition $𝒳$.

We now construct a tree decomposition ${𝒳}^{\prime }=(T,{ℬ}^{\prime })$ for the dual graph of ${𝒯}^{\ast }$, with the same underlying tree $T$ as for $𝒳$ and ${ℬ}^{\prime }=\{B_{\tau }^{\prime }:\tau \in V(T)\}$. We initialize $B_{\tau }^{\prime }$ as $B_{\tau }^{\prime }=\mathrm{\varnothing }$ for all $\tau \in V(T)$, and consider all types of tetrahedra $\sigma$ in ${𝒯}^{\ast }$:

1. 1.

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

2. 2.

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

3. 3.

   If $\sigma$ has a face $\{w,v_{\mathrm{\ell }-1},v_{\mathrm{\ell }}\}$, then add $\sigma$ to all bags $B_{\tau }^{\prime }$ such that $B_{\tau }$ contains any $u_i$ with .

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

Vertex coverage.

By construction, any tetrahedron of ${𝒯}^{\ast }$ contains a triangle from a 2-face $F$ of the spine $S$, and in consequence appears in some bag of ${𝒳}^{\prime }=(T,{ℬ}^{\prime })$.

Edge coverage.

Showing that every edge of ${𝒯}^{\ast }$ is contained in some bag of ${𝒳}^{\prime }$ can be carried out by a tedious case analysis. In the triangulation ${𝒯}^{\ast }$, 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 the full version [18] for all the details.

Subtree property.

By 1 and 2, tetrahedra of type $\{a,v_{\mathrm{\ell }},u_i,u_{i+1}\}$, $\{a,v_{\mathrm{\ell }-1},u_{\mathrm{\ell }(d-1)},v_{\mathrm{\ell }}\}$ and $\{a,v_{m-1},u_0,v_0\}$ appear exactly in the bags $B_{\tau }^{\prime }$ such that $B_{\tau }$ contain a certain fixed tetrahedron (respectively $u_i$, $u_{\mathrm{\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_{\mathrm{\ell }-1},v_{\mathrm{\ell }}\}$ is inserted in all bags $B_{\tau }^{\prime }$ such that $B_{\tau }$ contains any $u_i$ with . Call $T_i$ the subtree of $T$ spanned by the nodes $\tau$ such that $u_i\in B_{\tau }$ in $𝒳$. The subtree of $T$ spanned by the nodes $\tau$ in ${𝒳}^{\prime }$ such that $\sigma \in B_{\tau }$ is, in consequence, . Because $𝒳$ 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 $𝒳$. Hence $T_i\cap T_{i+1}\ne \mathrm{\varnothing }$. In consequence, is a connected subtree of $\sigma$.

$\mathrm{⊲}$

Let $B_{\tau }$ be a bag of $𝒳$ 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 }^{\prime }$, per 2-face incident to $u_i$, namely tetrahedra $(\star ,v_{\mathrm{\ell }},u_i,u_{i+1}\}$, tetrahedra $(\star ,v_{\mathrm{\ell }},u_i,v_{\mathrm{\ell }+1}\}$ if $i=\mathrm{\ell }(d-1)$ or $i=0$, and tetrahedra $(\star ,w,v_{\mathrm{\ell }-1},v_{\mathrm{\ell }}\}$ with $\mathrm{\ell }(d-1)\le i\le \max \{(\mathrm{\ell }+1)(d-1)-1,k-1\}$; where $\star$ indicates at most two possible vertices $a$ and $b$ of $𝒯(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 }^{\prime }$ is at most $36$ times the size of $B_{\tau }$. In consequence, the width of ${𝒳}^{\prime }$ is at most $36\cdot (\mathrm{𝐭𝐰}+1)-1$. This concludes the proofs of Claim 12 and Lemma 10. $\mathrm{⊲}$ $◀$

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

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

$◀$

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

With $|𝒯(0)|=𝐯$ and the $n$ vertices $u_i$, this gives at most $(6+\sqrt{6})(n+𝐯)$ vertices in ${𝒯}^{\ast }$. $◀$

We are now ready to prove the main theorems of this section.

If the maximum edge valence of $𝒯$ is at most $9$, the algorithm simply returns ${𝒯}^{\ast }:=𝒯$. 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 ${𝒯}^{\ast }$, which is $O(n)$. $◀$

Finally, the proof of Theorem 5 relies on standard calculations involving geometric series and iterated radicals, as detailed in the full version [18].

If the maximum edge valence of $𝒯$ satisfies $\mathrm{\Delta }(𝒯)\le 9$, we are done. Otherwise, we construct a sequence of triangulations $𝒯={𝒯}_0,{𝒯}_1,\mathrm{\dots },{𝒯}_p$ by iterating the construction of Theorem 6. The triangulation ${𝒯}_r$ has $O({(30+4\sqrt{6})}^r(n+𝐯))$ tetrahedra and vertices [18, Lemma 23], treewidth (Lemma 10), and maximum edge valence $\mathrm{\Delta }({𝒯}_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 [18, Lemma 21], with $a_0=𝚫$, $c=4$, and . By [18, Lemma 22], choosing $p={\log }_2{\log }_2(𝚫)$ ensures that the edge valence of ${𝒯}_p$ is at most $9$. We therefore set ${𝒯}^{\ast }:={𝒯}_p$. Since and , the triangulation ${𝒯}^{\ast }$ has $O((n+𝐯){\log }_2{(𝚫)}^{5.32})$ tetrahedra and vertices, treewidth at most $(\mathrm{𝐭𝐰}+1)\cdot {\log }_2{(𝚫)}^{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. $◀$

A Hopf algebra $\mathscr{H}$ is a vector space $𝑯$ over a field $𝔽$ together with three $𝔽$-linear maps $𝖬:𝑯\otimes 𝑯\to 𝑯$ (multiplication), $\mathsf{\Delta }:𝑯\to 𝑯\otimes 𝑯$ (comultiplication) and $𝖲:𝑯\to 𝑯$ (antipode) satisfying certain axioms (cf. [23, Section 3]). We will assume that and $\mathscr{H}$ is involutory, i.e., $𝖲\circ 𝖲={\mathrm{id}}_{𝑯}$. The maps $𝖬$, $\mathsf{\Delta }$ and $𝖲$ can be regarded as tensors of type $(1,2)$, $(2,1)$ and $(1,1)$, respectively, see Figure 11.