\definecolor

BrickRedrgb0.714,0.196,0.11 \definecolorBluergb0.176,0.184,0.573 Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France and \urlhttps://kristofhuszar.github.io/[email protected]://orcid.org/0000-0002-5445-5057Supported by the French National Research Agency through the 3IA Côte d’Azur (ANR-19-P3IA-0002), AlgoKnot (ANR-20-CE48-0007), GrR (ANR-18-CE40-0032), and TWIN-WIDTH (ANR-21-CE48-0014) projects. A previous version of this manuscript was written during the author’s visit at Institut Henri Poincaré (IHP). The author acknowledges the hospitality of IHP (UAR 839 CNRS–Sorbonne Université) and LabEx CARMIN (ANR-10-LABX-59-01). School of Mathematics and Statistics F07, The University of Sydney, NSW 2006 Australia and \urlhttps://sites.google.com/view/jonathan-spreer/[email protected]://orcid.org/0000-0001-6865-9483Supported by the Australian Research Council’s Discovery funding scheme (project no. DP220102588). \CopyrightKristóf Huszár and Jonathan Spreer \ccsdesc[500]Mathematics of computing Geometric topology \ccsdesc[300]Theory of computation Problems, reductions and completeness \ccsdesc[300]Theory of computation Fixed parameter tractability

Acknowledgements.

We are grateful to Arnaud de Mesmay and to Clément Maria for their interest in our work and for inspiring discussions. We thank the anonymous referees for several suggestions to improve this article. \nolinenumbers\hideLIPIcs\EventEditorsErin W. Chambers and Joachim Gudmundsson \EventNoEds2 \EventLongTitle39th International Symposium on Computational Geometry (SoCG 2023) \EventShortTitleSoCG 2023 \EventAcronymSoCG \EventYear2023 \EventDateJune 12–15, 2023 \EventLocationDallas, Texas, USA \EventLogosocg-logo.pdf \SeriesVolume258 \ArticleNoXX

On the Width of Complicated JSJ Decompositions

Kristóf Huszár Jonathan Spreer

Abstract

Motivated by the algorithmic study of 3-dimensional manifolds, we explore the structural relationship between the JSJ decomposition of a given 3-manifold and its triangulations. Building on work of Bachman, Derby-Talbot and Sedgwick, we show that a “sufficiently complicated” JSJ decomposition of a 3-manifold enforces a “complicated structure” for all of its triangulations. More concretely, we show that, under certain conditions, the treewidth (resp. pathwidth) of the graph that captures the incidences between the pieces of the JSJ decomposition of an irreducible, closed, orientable 3-manifold $\mathscr{M}$ yields a linear lower bound on its treewidth $\operatorname{tw}(\mathscr{M})$ (resp. pathwidth $\operatorname{pw}(\mathscr{M})$ ), defined as the smallest treewidth (resp. pathwidth) of the dual graph of any triangulation of $\mathscr{M}$ .

We present several applications of this result. We give the first example of an infinite family of bounded-treewidth 3-manifolds with unbounded pathwidth. We construct Haken 3-manifolds with arbitrarily large treewidth—previously the existence of such 3-manifolds was only known in the non-Haken case. We also show that the problem of providing a constant-factor approximation for the treewidth (resp. pathwidth) of bounded-degree graphs efficiently reduces to computing a constant-factor approximation for the treewidth (resp. pathwidth) of 3-manifolds.

keywords:

computational 3-manifold topology, fixed-parameter tractability, generalized Heegaard splittings, JSJ decompositions, pathwidth, treewidth, triangulations

1 Introduction

Manifolds in geometric topology are often studied through the following two-step process. Given a piecewise linear $d$ -dimensional manifold $\mathscr{M}$ , first find a “suitable” triangulation of it, i.e., a decomposition of $\mathscr{M}$ into $d$ -simplices with “good” combinatorial properties. Then apply algorithms on this triangulation to reveal topological information about $\mathscr{M}$ .

The work presented in this article is motivated by this process in dimension $d=3$ . Here every manifold can be triangulated [43] and questions about them typically admit algorithmic solutions [34, 38, 53].¹¹1In higher dimensions none of these statements is true in general. See, e.g., [40], [42] or [45, Section 7]. At the same time, the feasibility of a particular computation can greatly depend on structural properties of the triangulation in use. Over the past decade, this phenomenon was recognized and exploited in various settings, leading to fixed-parameter tractable (FPT) algorithms for several problems in low-dimensional topology, some of which are even known to be NP-hard [14, 15, 16, 17, 18].²²2See [8] for an FPT algorithm checking tightness of (weak) pseudomanifolds in arbitrary dimensions. Although these algorithms have exponential running time in the worst case, for input triangulations with dual graph of bounded treewidth they always terminate in polynomial (in most cases, linear) time.³³3The running times are given in terms of the size of the input triangulation, i.e., its number of tetrahedra. Moreover, some of them have implementations that are highly effective in practice, providing useful tools for researchers in low-dimensional topology [12, 13].

The theoretical efficiency of the aforementioned FPT algorithms crucially depends on the assumption that the dual graph of the input triangulation has small treewidth. To understand their scope, it is thus instructive to consider the treewidth $\operatorname{tw}(\mathscr{M})$ of a compact $3$ -manifold $\mathscr{M}$ , defined as the smallest treewidth of the dual graph of any triangulation of $\mathscr{M}$ . Indeed, the relation between the treewidth and other quantities associated with 3-manifolds has recently been investigated in various contexts [25, 26, 27, 28, 41]. For instance, in [28] together with Wagner we have shown that the treewidth of a non-Haken 3-manifold is always bounded below in terms of its Heegaard genus. Combined with earlier work of Agol [1]—who constructed non-Haken 3-manifolds with arbitrary large Heegaard genus—this implies the existence of 3-manifolds with arbitrary large treewidth. Despite the fact that, asymptotically, most triangulations of most 3-manifolds must have dual graph of large treewidth [28, Appendix A], this collection described by Agol has remained, to this date, the only known family of 3-manifolds with arbitrary large treewidth.

The main result

In this work we unravel new structural links between the triangulations of a given 3-manifold and its JSJ decomposition [30, 31, 32]. Employing the machinery of generalized Heegaard splittings [49], the results developed in [28], and building on the work of Bachman, Derby-Talbot and Sedgwick [5, 6], we show that, under suitable conditions, the dual graph of any triangulation of a given 3-manifold $\mathscr{M}$ inherits structural properties from the decomposition graph that encodes the incidences between the pieces of the JSJ decomposition of $\mathscr{M}$ . More precisely, in \Crefsec:main we prove the following theorem.

Theorem 1.1 (Width inheritance).

For any closed, orientable and irreducible $3$ -manifold $\mathscr{M}$ with sufficiently complicated⁴⁴4The notion of “sufficiently complicated” under which we establish Theorem 1.1 is discussed in \Crefsec:main. torus gluings in its JSJ decomposition $\mathscr{D}$ , the treewidth and pathwidth of $\mathscr{M}$ and that of the decomposition graph $\Gamma(\mathscr{D})$ of $\mathscr{D}$ satisfy

\operatorname{tw}(\Gamma(\mathscr{D}))\leq 18\cdot(\operatorname{tw}(\mathscr{M})+1)

(1)

and

\operatorname{pw}(\Gamma(\mathscr{D}))\leq 4\cdot(3\operatorname{pw}(\mathscr{M})+1).

(2)

An algorithmic construction

Much work in 3-dimensional topology has been devoted to the study of 3-manifolds constructed by pasting together simpler pieces along their boundary surfaces via “sufficiently complicated” gluing maps, and to understand how different decompositions of the same 3-manifold interact under various conditions, see, e.g., [4, 5, 6, 7, 35, 39, 47, 52]. \Crefthm:jsj-width allows us to leverage these results to construct 3-manifolds, where we have tight control over the treewidth and pathwidth of their triangulations [25].

By combining \Crefthm:jsj-width and [4, Theorem 5.4] (cf. [6, Appendix]), in \Crefsec:const we prove the following result.

Theorem 1.2.

There is a polynomial-time algorithm that, given an $n$ -node graph $G$ with maximum node-degree $\Delta$ , produces a triangulation $\mathscr{T}_{G}$ of a closed $3$ -manifold $\mathscr{M}_{G}$ , such that

1.

the triangulation $\mathscr{T}_{G}$ contains $O_{\Delta}(\operatorname{pw}(G)\cdot n)$ tetrahedra,⁵⁵5Similar to the standard big-O notation, $O_{\Delta}(x)$ means “a quantity bounded above by $x$ times a constant depending on $\Delta$ .” To ensure that \colorlipicsGray3a is satisfied, but not necessarily \colorlipicsGray3b, $O_{\Delta}(\operatorname{tw}(G)\cdot n)$ tetrahedra suffice.
2.

the JSJ decomposition $\mathscr{D}$ of $\mathscr{M}_{G}$ satisfies $\Gamma(\mathscr{D})=G$ , and
3.
there exist universal constants $c,c^{\prime}>0$ , such that
1. (a)
  
  $(c/\Delta)\operatorname{tw}(\mathscr{M}_{G})\leq\operatorname{tw}(G)\leq 18\cdot(\operatorname{tw}(\mathscr{M}_{G})+1)$ , and
2. (b)
  
  $(c^{\prime}/\Delta)\operatorname{pw}(\mathscr{M}_{G})\leq\operatorname{pw}(G)\leq 4\cdot(3\operatorname{pw}(\mathscr{M}_{G})+1)$ .

Applications

In \Crefsec:appl we present several applications of \Crefthm:construction. First, we construct a family of bounded-treewidth 3-manifolds with unbounded pathwidth (\Crefcor:unbounded-pathwidth). Second, we exhibit Haken 3-manifolds with arbitrary large treewidth (\Crefcor:unbounded-treewidth). To our knowledge, no such families of 3-manifolds had been known before. Third, we show that the problem of providing a constant-factor approximation for the treewidth (resp. pathwidth) of bounded-degree graphs reduces in polynomial time to computing a constant-factor approximation for the treewidth (resp. pathwidth) of 3-manifolds (\Crefcor:hardness-treewidth). This reduction, together with previous results [46, 55, 56], suggests that this problem may be computationally hard.

Proof 1.3 (Outline of the proof of Theorem 1.1).

We now give a preview of the proof of our main result. As the arguments for showing (1) and (2) are analogous, we only sketch the proof of (1). To show that $\operatorname{tw}(\Gamma(\mathscr{D}))\leq 18(\operatorname{tw}(\mathscr{M})+1)$ , we start with a triangulation $\mathscr{T}$ of $\mathscr{M}$ whose dual graph has minimal treewidth, i.e., $\operatorname{tw}(\Gamma(\mathscr{T}))=\operatorname{tw}(\mathscr{M})$ . Following [28, Section 6], we construct from $\mathscr{T}$ a generalized Heegaard splitting $\mathscr{H}$ of $\mathscr{M}$ , together with a sweep-out $\Sigma=\{\Sigma_{x}:x\in H\}$ along a tree $H$ , such that the genus of any level surface $\Sigma_{x}$ is at most $18\cdot(\operatorname{tw}(\Gamma(\mathscr{T}))+1)$ . If $\mathscr{H}$ is not already strongly irreducible, we repeatedly perform weak reductions until we get a strongly irreducible generalized Heegaard splitting $\mathscr{H}^{\prime}$ with associated sweep-out $\Sigma^{\prime}=\{\Sigma^{\prime}_{x}:x\in H\}$ along the same tree $H$ . Crucially, weak reductions do not increase the genera of level surfaces [49, Section 5.2], thus $18\cdot(\operatorname{tw}(\Gamma(\mathscr{T}))+1)$ is still an upper bound on those in $\Sigma^{\prime}$ . Now, by the assumption of the JSJ decomposition of $\mathscr{M}$ being “sufficiently complicated,” each JSJ torus can be isotoped in $\mathscr{M}$ to coincide with a connected component of some thin level of $\mathscr{H}^{\prime}$ . This implies that, after isotopy, each level set $\Sigma^{\prime}_{x}$ is incident to at most $18\cdot(\operatorname{tw}(\Gamma(\mathscr{T}))+1)+1$ JSJ pieces of $\mathscr{M}$ . Sweeping along $H$ , we can construct a tree decomposition of $\Gamma(\mathscr{D})$ where each bag contains at most $18\cdot(\operatorname{tw}(\Gamma(\mathscr{T}))+1)+1$ nodes of $\Gamma(\mathscr{D})$ . Hence $\operatorname{tw}(\Gamma(\mathscr{D}))\leq 18\cdot(\operatorname{tw}(\Gamma(\mathscr{T}))+1)=18\cdot(\operatorname{tw}(\mathscr{M})+1)$ .

Organization of the paper

In \Crefsec:prelims we review the necessary background on graphs and 3-manifolds. \Crefsec:gen contains a primer on generalized Heegaard splittings, which provides us with the indispensable machinery for proving our main result (\Crefthm:jsj-width) in \Crefsec:main. In \Crefsec:const we describe the algorithmic construction of 3-manifolds that “inherit” their combinatorial width from that of their JSJ decomposition graph (\Crefthm:construction). Then, in \Crefsec:appl we present the aforementioned applications of this construction (\Crefcor:unbounded-pathwidth,cor:unbounded-treewidth,cor:hardness-treewidth). The paper is concluded with a discussion and some open questions in \Crefsec:discussion. Selected results from 3-manifold topology we rely on are collected in the \hyperref[app]Appendix.

2 Preliminaries

2.1 Graphs

A (multi)graph $G=(V,E)$ is a finite set $V=V(G)$ of nodes⁶⁶6Throughout this paper we use the terms edge and vertex to refer to an edge or vertex in a $3$ -manifold triangulation, whereas the terms arc and node denote an edge or vertex in a graph, respectively. together with a multiset $E=E(G)$ of unordered pairs of not necessarily distinct nodes, called arcs. The degree $d_{v}$ of a node $v\in V$ equals the number of arcs containing it, where loop arcs are counted twice. $G$ is $k$ -regular, if $d_{v}=k$ for all $v\in V$ . A tree is a connected graph with $n$ nodes and $n-1$ arcs.

A tree decomposition of a graph $G=(V,E)$ is a pair $(\mathscr{X}=\{B_{i}:i\in I\},T=(I,F))$ with bags $B_{i}\subseteq V$ and a tree $T=(I,F)$ , such that 1. $\bigcup_{i\in I}B_{i}=V$ (node coverage), 2. for all arcs $\{u,v\}\in E$ , there exists $i\in I$ such that $\{u,v\}\subseteq B_{i}$ (arc coverage), and 3. for all $v\in V$ , $T_{v}=\{i\in I:v\in B_{i}\}$ spans a connected sub-tree of $T$ (sub-tree property). The width of a tree decomposition equals $\max_{i\in I}|B_{i}|-1$ , and the treewidth $\operatorname{tw}(G)$ is the smallest width of any tree decomposition of $G$ . Replacing all occurrences of “tree” with “path” in the definition of treewidth yields the notion of pathwidth $\operatorname{pw}(G)$ . We have $\operatorname{tw}(G)\leq\operatorname{pw}(G)$ .

2.2 Manifolds

A $d$ -dimensional manifold is a topological space $\mathscr{M}$ , where each point $x\in\mathscr{M}$ has a neighborhood homeomorphic to $\mathbb{R}^{d}$ or to the closed upper half-space $\{(x_{1},\ldots,x_{d})\in\mathbb{R}^{d}:x_{d}\geq 0\}$ . The latter type of points of $\mathscr{M}$ constitute the boundary $\partial\mathscr{M}$ of $\mathscr{M}$ . A compact manifold is said to be closed if it has an empty boundary. We consider manifolds up to homeomorphism (“continuous deformations”) and write $\mathscr{M}_{1}\cong\mathscr{M}_{2}$ for homeomorphic manifolds $\mathscr{M}_{1}$ and $\mathscr{M}_{2}$ .

3-Manifolds and surfaces

The main objects of study in this paper are 3-dimensional manifolds, or $3$ -manifolds for short. Here we give a brief introduction to $3$ -manifolds tailored to our purposes. We refer the reader to [51] (and the references therein) for more details. All 3-manifolds and surfaces encountered in this article are compact and orientable. We let $\mathbb{S}_{g}$ denote the closed, connected, orientable surface of genus $g$ . We also refer to the $d$ -dimensional torus and sphere as $\mathbb{T}^{d}$ and $\mathbb{S}^{d}$ , respectively (hence $\mathbb{S}_{0}=\mathbb{S}^{2}$ and $\mathbb{S}_{1}=\mathbb{T}^{2}$ ). The genus $g(\mathcal{S})$ of a (not necessarily connected) surface $\mathcal{S}$ is defined to be the sum of the genera of its connected components.

Triangulations and the treewidth of 3-manifolds

A triangulation $\mathscr{T}$ of a given $3$ -manifold $\mathscr{M}$ is a finite collection of abstract tetrahedra glued together along pairs of their triangular faces, such that the resulting space is homeomorphic to $\mathscr{M}$ . Unpaired triangles comprise a triangulation of the boundary of $\mathscr{M}$ . Note that the face gluings may also identify several tetrahedral edges (or vertices) in a single edge (or vertex) of $\mathscr{T}$ . Every compact 3-manifold admits a triangulation [43] (cf. [10]). Given a triangulation $\mathscr{T}$ , its dual graph $\Gamma(\mathscr{T})$ is the multigraph whose nodes correspond to the tetrahedra in $\mathscr{T}$ , and arcs to face gluings (\Creffig:tetrahedra).

Refer to caption — Figure 1: (i) Example of a triangulation $\mathscr{T}$ with two tetrahedra $\Delta_{1}$ and $\Delta_{2}$ , and three face gluing maps $\varphi_{1}$ , $\varphi_{2}$ and $\varphi_{3}$ . The map $\varphi_{1}$ is specified to be $\Delta_{1}(123)\longleftrightarrow\Delta_{2}(103)$ . (ii) The dual graph $\Gamma(\mathscr{T})$ of the triangulation $\mathscr{T}$ . Reproduced from [26, Figure 1].

For a compact 3-manifold $\mathscr{M}$ , its treewidth $\operatorname{tw}(\mathscr{M})$ (resp. pathwidth $\operatorname{pw}(\mathscr{M})$ ) is defined as the smallest treewidth (resp. pathwidth) of the dual graph of any triangulation of $\mathscr{M}$ .

Incompressible surfaces and essential disks

Given a $3$ -manifold $\mathscr{M}$ , a surface $\mathcal{S}\subset\mathscr{M}$ is said to be properly embedded in $\mathscr{M}$ if $\partial\mathcal{S}\subset\partial\mathscr{M}$ and $(\mathcal{S}\setminus\partial\mathcal{S})\subset(\mathscr{M}\setminus\partial\mathscr{M})$ . Given a properly embedded surface $\mathcal{S}\subset\mathscr{M}$ , an embedded disk $D\subset\mathscr{M}$ with $\operatorname{int}(D)\cap\mathcal{S}=\emptyset$ and $\partial D\subset\mathcal{S}$ a curve not bounding a disk on $\mathcal{S}$ is called a compressing disk. If such a disk exists, $\mathcal{S}$ is said to be compressible in $\mathscr{M}$ , otherwise – and if $\mathcal{S}$ is not a $2$ -sphere – it is called incompressible. A $3$ -manifold $\mathscr{M}$ is said to be irreducible, if every embedded $2$ -sphere bounds a $3$ -ball in $\mathscr{M}$ . A disk $D\subset\mathscr{M}$ properly embedded in a 3-manifold $\mathscr{M}$ is called inessential if it cuts off a 3-ball from $\mathscr{M}$ , otherwise $D$ is called essential. A compact, orientable, irreducible $3$ -manifold is called Haken if it contains an orientable, properly embedded, incompressible surface, and otherwise is referred to as non-Haken.

Heegaard splittings of closed 3-manifolds

A handlebody $\mathcal{H}$ is a connected $3$ -manifold homeomorphic to a thickened graph. The genus $g(\mathcal{H})$ of $\mathcal{H}$ is defined as the genus of its boundary surface $\partial\mathcal{H}$ . A Heegaard splitting of a closed, orientable 3-manifold $\mathscr{M}$ is a decomposition $\mathscr{M}=\mathcal{H}\cup_{\mathcal{S}}\mathcal{H}^{\prime}$ where $\mathcal{H}$ and $\mathcal{H}^{\prime}$ are homeomorphic handlebodies with $\mathcal{H}\cup\mathcal{H}^{\prime}=\mathscr{M}$ and $\mathcal{H}\cap\mathcal{H}^{\prime}=\partial\mathcal{H}=\partial\mathcal{H}^{\prime}=\mathcal{S}$ called the splitting surface. Introduced in [24], the Heegaard genus $\mathfrak{g}\left(\mathscr{M}\right)$ of $\mathscr{M}$ is the smallest genus $g(\mathcal{S})$ over all Heegaard splittings of $\mathscr{M}.$

The JSJ decomposition

A central result by Jaco–Shalen [30, 31] and Johannson [32] asserts that every closed, irreducible and orientable 3-manifold $\mathscr{M}$ admits a collection $\mathbf{T}$ of pairwise disjoint embedded, incompressible tori, where each piece of the complement $\mathscr{M}\setminus\mathbf{T}$ is either Seifert fibered⁷⁷7See [51, Section 3.7] or [23, p. 18] for an introduction to Seifert fibered spaces (cf. \Crefapp:jsj). or atoroidal⁸⁸8An irreducible 3-manifold $\mathscr{M}$ is called atoroidal if every incompressible torus in $\mathscr{M}$ is boundary-parallel.. A minimal such collection of tori is unique up to isotopy and gives rise to the so-called JSJ decomposition (or torus decomposition) of $\mathscr{M}$ [23, Theorem 1.9]. We refer to this collection of incompressible tori as the JSJ tori of $\mathscr{M}$ . The graph with nodes the JSJ pieces, and an arc for each JSJ torus (with endpoints the two nodes corresponding to its two adjacent pieces) is called the dual graph $\Gamma(\mathscr{D})$ of the JSJ decomposition $\mathscr{D}$ of $\mathscr{M}$ .

3 Generalized Heegaard Splittings

A Heegaard splitting of a closed 3-manifold is a decomposition into two identical handlebodies along an embedded surface. Introduced by Scharlemann and Thompson [50], a generalized Heegaard splitting of a compact 3-manifold $\mathscr{M}$ (possibly with boundary) is a decomposition of $\mathscr{M}$ into several pairs of compression bodies along a family of embedded surfaces, subject to certain rules. Following [49, Chapters 2 and 5],⁹⁹9For an open-access version, see [48, Sections 3.1 and 4]. here we give an overview of this framework.

3.1 Compression bodies and forks

A compression body $\mathcal{C}$ is a 3-manifold with boundary obtained by the following procedure.

1.

Consider the thickening $\mathcal{S}\times[0,1]$ of a closed, orientable, possibly disconnected surface $\mathcal{S}$ ,
2.

optionally attach some $1$ -handles, each being of the form $D\times[0,1]$ (thickened edge, where the disk $D$ is the cross-section), to $\mathcal{S}\times\{1\}$ along $D\times\{0\}\cup D\times\{1\}$ , and
3.

optionally fill in some collection of $2$ -sphere components of $\mathcal{S}\times\{0\}$ with $3$ -balls.

We call $\partial_{-}\mathcal{C}=\mathcal{S}\times\{0\}\setminus\{\text{filled-in 2-sphere components}\}$ the lower boundary of $\mathcal{C}$ and $\partial_{+}\mathcal{C}=\partial\,\mathcal{C}\setminus\partial_{-}\mathcal{C}$ its upper boundary. By construction, $g(\partial_{+}\mathcal{C})\geq g(\partial_{-}\mathcal{C})$ . Note that, if $\partial_{-}\mathcal{C}$ is empty, then $\mathcal{C}$ is a handlebody. We allow compression bodies to be disconnected.

A fork, more precisely an $n$ -fork, $F$ is a tree with $n+2$ nodes $V(F)=\{\rho,\gamma,\tau_{1},\ldots,\tau_{n}\}$ , where $\rho$ , called the root, is of degree $n+1$ , and the other nodes are leaves. One of them, denoted $\gamma$ , is called the grip, and the remaining leaves $\tau_{1},\ldots,\tau_{n}$ are called tines. A fork can be regarded as an abstraction of a connected compression body $\mathcal{C}$ , where the grip corresponds to $\partial_{+}\mathcal{C}$ and each tine corresponds to a connected component of $\partial_{-}\mathcal{C}$ , see, e.g., \Creffig:compbody.

Non-faithful forks

In certain situations (notably, in the proof of \Crefthm:jsj-width, cf. \Crefsec:main) it is useful to also take a simplified view on a generalized Heegaard splitting. To that end, one may represent several compression bodies by a single non-faithful fork, where the grip and the tines may correspond to collections of boundary components. To distinguish faithful forks from non-faithful ones, we color the roots of the latter with gray, see \Creffig:faithful-forks.

\nolinenumbers

\begin{overpic}[scale={.9}]{faithful-forks} \put(57.5,29.85){\Large$\leadsto$} \end{overpic}\captionof

figureTwo faithful forks bundled into a non-faithful fork. The colors show the grouping of the tines.

\begin{overpic}[scale={.9}]{compbody-spine} \put(47.25,40.25){$\Gamma$} \put(-10.0,1.0){$\mathcal{C}$} \put(102.0,1.0){$\mathcal{H}$} \end{overpic}\captionof

figure\nolinenumbersSpines of a compression body $\mathcal{C}$ and of a handlebody $\mathcal{H}$ .

Spines and sweep-outs of compression bodies

A graph $\Gamma$ embedded in a compression body $\mathcal{C}$ is called a spine of $\mathcal{C}$ , if every node of $\Gamma$ that is incident to $\partial_{-}\mathcal{C}$ is of degree one, and $\mathcal{C}\setminus(\Gamma\cup\partial_{-}\mathcal{C})\cong\partial_{+}\mathcal{C}\times(0,1]$ , see \Creffig:compbody-spine. Assume first that $\partial_{-}\mathcal{C}\neq\emptyset$ . A sweep-out of $\mathcal{C}$ along an interval, say $[-1,1]$ , is a continuous map $f\colon\mathcal{C}\rightarrow[-1,1]$ , such that $f^{-1}(\pm 1)=\partial_{\pm}\mathcal{C}$ ,

\displaystyle f^{-1}(t)\cong\begin{cases}\partial_{+}\mathcal{C},&\text{if}\phantom{-}t\in(0,1),\\ \Gamma\cup\partial_{-}\mathcal{C},&\text{if}\phantom{-}t=0,~{}\text{and}\\ \partial_{-}\mathcal{C},&\text{if}\phantom{-}t\in(-1,0).\end{cases}

(3)

Writing $\Sigma_{t}=f^{-1}(t)$ , we get a 1-parameter family of surfaces (except for $\Sigma_{0}$ ) “sweeping through” $\mathcal{C}$ . For handlebodies, the definition of a sweep-out is similar, but it “ends at $0$ ” with the spine: $f^{-1}(1)=\partial\mathcal{H}$ , $f^{-1}(t)\cong\partial\mathcal{H}$ if $t\in(0,1)$ , and $f^{-1}(0)=\Gamma$ , see \Creffig:sweep-out.

{subfigure}

[b]0.48 \begin{overpic}[scale={.9}]{sweep-out-compbody-2} \put(0.0,32.75){\small{$\phantom{-}1\phantom{-}$}} \put(0.0,17.5){\small{$\phantom{-}0\phantom{-}$}} \put(0.0,3.25){\small{$-1\phantom{-}$}} \put(88.0,32.75){\small{$\Sigma_{1}$}} \put(88.0,17.5){\small{$\Sigma_{0}$}} \put(88.0,3.25){\small{$\Sigma_{-1}$}} \end{overpic} {subfigure}[b]0.48 \begin{overpic}[scale={.9}]{sweep-out-hbody} \put(0.0,32.75){\small{$\phantom{1/}1$}} \put(0.0,17.5){\small{$1/2$}} \put(0.0,3.25){\small{$\phantom{1/}0$}} \put(88.0,32.75){\small{$\Sigma_{1}$}} \put(88.0,17.5){\small{$\Sigma_{1/2}$}} \put(88.0,3.25){\small{$\Sigma_{0}$}} \end{overpic}

Figure 6: Sweep-outs of the compression body

\mathcal{C}

and of the handlebody

\mathcal{H}

shown in \Creffig:compbody-spine.

Remark 3.1 (Sweep-out along a fork).

It is straightforward to adapt the definition of sweep-out in a way that, instead of an interval, we sweep a compression body $\mathcal{C}$ along a (faithful or non-faithful) fork $F$ . Such a sweep-out is a continuous map $f\colon\mathcal{C}\rightarrow\|F\|$ (where $\|F\|$ denotes a geometric realization of $F$ ) that satisfies very similar requirements to those in (3), however, the components of the lower boundary $\partial_{-}\mathcal{C}$ may appear in different level sets, see \Creffig:sweep-out-fork.

{subfigure}

[b]0.48 \begin{overpic}[scale={.9}]{sweep-out-compbody-gray} \put(0.0,32.75){\small{$\phantom{-}1\phantom{-}$}} \put(0.0,17.5){\small{$\phantom{-}0\phantom{-}$}} \put(0.0,3.25){\small{$-1\phantom{-}$}} \put(88.0,32.75){\small{$\Sigma_{1}$}} \put(88.0,17.5){\small{$\Sigma_{0}$}} \put(88.0,3.25){\small{$\Sigma_{-1}$}} \end{overpic} {subfigure}[b]0.48 \begin{overpic}[scale={.9}]{sweep-out-compbody-color} \put(4.25,33.25){\small{grip}} \put(4.0,18.0){\small{root}} \put(2.5,3.75){\small{tines}} \put(88.0,32.75){\small{$\Sigma_{\gamma}$}} \put(88.0,17.5){\small{$\Sigma_{\rho}$}} \put(88.0,3.25){\small{$\Sigma_{\tau_{1}}\cup\Sigma_{\tau_{2}}$}} \end{overpic}

Figure 7: Sweep-out of a compression body along

[-1,1]

(left) and along its faithful fork (right).

3.2 Generalized Heegaard splittings and fork complexes

Heegaard splittings revisited

Let $\mathscr{M}$ be a 3-manifold, and $\{\partial_{1}\mathscr{M},\partial_{2}\mathscr{M}\}$ be a partition of the components of $\partial\mathscr{M}$ . A Heegaard splitting of $(\mathscr{M},\partial_{1}\mathscr{M},\partial_{2}\mathscr{M})$ is a triplet $(\mathcal{C}_{1},\mathcal{C}_{2},\mathcal{S})$ , where $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ are compression bodies with $\mathcal{C}_{1}\cup\mathcal{C}_{2}=\mathscr{M}$ , $\mathcal{C}_{1}\cap\mathcal{C}_{1}=\partial_{+}\mathcal{C}_{1}=\partial_{+}\mathcal{C}_{2}=\mathcal{S}$ , $\partial_{-}\mathcal{C}_{1}=\partial_{1}\mathscr{M}$ , and $\partial_{-}\mathcal{C}_{2}=\partial_{2}\mathscr{M}$ . The genus of the Heegaard splitting $(\mathcal{C}_{1},\mathcal{C}_{2},\mathcal{S})$ is the genus $g(\mathcal{S})$ of the splitting surface $\mathcal{S}$ . The Heegaard genus $\mathfrak{g}\left(\mathscr{M}\right)$ of $\mathscr{M}$ is the smallest genus of any Heegaard splitting of $(\mathscr{M},\partial_{1}\mathscr{M},\partial_{2}\mathscr{M})$ , taken over all partitions $\{\partial_{1}\mathscr{M},\partial_{2}\mathscr{M}\}$ of $\partial\mathscr{M}$ .

\begin{overpic}[scale={.7}]{heegaard-splitting-boundary} \put(-1.0,6.0){\small{$\partial_{1}\mathscr{M}$}} \put(13.75,6.0){\small{$\mathscr{M}$}} \put(22.75,6.0){\small{$\partial_{2}\mathscr{M}$}} \put(31.5,6.0){\small{$\partial_{-}\mathcal{C}_{1}$}} \put(38.0,1.0){\scalebox{1.4}{\rotatebox{90.0}{$\Bigg{\{}$}}} \put(42.75,-1.25){\small{$\mathcal{C}_{1}$}} \put(48.5,9.5){\small{$\mathcal{S}$}} \put(49.75,1.0){\scalebox{1.4}{\rotatebox{90.0}{$\Bigg{\{}$}}} \put(54.5,-1.25){\small{$\mathcal{C}_{2}$}} \put(63.0,6.0){\small{$\partial_{-}\mathcal{C}_{2}$}} \put(71.75,8.75){\small{$\partial_{-}\mathcal{C}_{1}$}} \put(74.5,1.0){\scalebox{1.4}{\rotatebox{90.0}{$\Bigg{\{}$}}} \put(79.25,-1.25){\small{$\mathcal{C}_{1}$}} \put(85.0,9.5){\small{$\mathcal{S}$}} \put(86.25,1.0){\scalebox{1.4}{\rotatebox{90.0}{$\Bigg{\{}$}}} \put(91.0,-1.25){\small{$\mathcal{C}_{2}$}} \put(95.25,8.75){\small{$\partial_{-}\mathcal{C}_{2}$}} \end{overpic}

Figure 8: Schematic of a

3

-manifold

\mathscr{M}

with a partition of its boundary components (left). Faithful (center) and non-faithful (right) fork complexes representing a Heegaard splitting of

(\mathscr{M},\partial_{1}\mathscr{M},\partial_{2}\mathscr{M})

Proposition 3.2 ([49, Theorem 2.1.11], cf. [26, Appendix B]).

For any partition $\{\partial_{1}\mathscr{M},\partial_{2}\mathscr{M}\}$ of the boundary components of $\mathscr{M}$ , there exists a Heegaard splitting of $(\mathscr{M},\partial_{1}\mathscr{M},\partial_{2}\mathscr{M})$ .

Generalized Heegaard splittings

A generalized Heegaard splitting $\mathscr{H}$ of a $3$ -manifold $\mathscr{M}$ consists of 1. a decomposition $\mathscr{M}=\bigcup_{i\in I}\mathscr{M}_{i}$ into submanifolds $\mathscr{M}_{i}\subseteq\mathscr{M}$ intersecting along closed surfaces (\Creffig:manifold-decomp), 2. for each $i\in I$ a partition $\{\partial_{1}\mathscr{M}_{i},\partial_{2}\mathscr{M}_{i}\}$ of the components of $\partial\mathscr{M}_{i}$ that together satisfy an acyclicity condition: there is an ordering, i.e., a bijection $\ell\colon I\rightarrow\{1,\ldots,|I|\}$ , such that, for each $i\in I$ the components of $\partial_{1}\mathscr{M}_{i}$ (resp. $\partial_{2}\mathscr{M}_{i}$ ) not belonging to $\partial\mathscr{M}$ are only incident to submanifolds $\mathscr{M}_{j}$ with $\ell(j)<\ell(i)$ (resp. $\ell(j)>\ell(i)$ ), and 3. a choice of a Heegaard splitting $(\mathcal{C}^{(i)}_{1},\mathcal{C}^{(i)}_{2},\mathcal{S}_{i})$ for each $(\mathscr{M}_{i},\partial_{1}\mathscr{M}_{i},\partial_{2}\mathscr{M}_{i})$ . Such a choice of splitting surfaces $\mathcal{S}_{i}$ $(i\in I)$ is said to be compatible with $\ell$ , see, e.g., \Creffig:gen-heegaard.

{subfigure}

[b]0.29 \begin{overpic}[scale={.9}]{manifold-decomp} \put(15.0,44.0){\small{$\mathscr{M}_{2}$}} \put(25.0,15.0){\small{$\mathscr{M}_{1}$}} \put(75.0,46.0){\small{$\mathscr{M}_{4}$}} \put(73.0,16.0){\small{$\mathscr{M}_{3}$}} \put(10.0,28.0){\small{$\mathcal{R}_{1}$}} \put(48.5,-10.0){\small{$\mathcal{R}_{2}$}} \put(45.0,61.0){\small{$\mathcal{R}_{3}$}} \put(82.5,31.5){\small{$\mathcal{R}_{4}$}} \end{overpic} {subfigure}[b]0.29 \begin{overpic}[scale={.9}]{gen-heegaard} \put(18.0,45.25){\small{$\mathcal{S}_{2}$}} \put(17.25,17.25){\small{$\mathcal{S}_{1}$}} \put(75.25,47.25){\small{$\mathcal{S}_{4}$}} \put(72.0,16.5){\small{$\mathcal{S}_{3}$}} \put(-4.0,-5.0){\footnotesize{$\partial_{1}\mathscr{M}_{1}=\emptyset$}} \put(-4.0,-15.0){\footnotesize{$\partial_{2}\mathscr{M}_{1}=\mathcal{R}_{1}\cup\mathcal{R}_{2}$}} \put(67.0,-5.0){\footnotesize{$\partial_{1}\mathscr{M}_{3}=\mathcal{R}_{2}$}} \put(67.0,-15.0){\footnotesize{$\partial_{2}\mathscr{M}_{3}=\mathcal{R}_{4}$}} \put(-4.0,75.0){\footnotesize{$\partial_{1}\mathscr{M}_{2}=\mathcal{R}_{1}$}} \put(-4.0,65.0){\footnotesize{$\partial_{2}\mathscr{M}_{2}=\mathcal{R}_{3}$}} \put(47.0,75.0){\footnotesize{$\partial_{1}\mathscr{M}_{4}=\mathcal{R}_{3}\cup\mathcal{R}_{4}$}} \put(47.0,65.0){\footnotesize{$\partial_{2}\mathscr{M}_{4}=\emptyset$}} \end{overpic} {subfigure}[b]0.29 \begin{overpic}[scale={.9}]{fork-comp} \put(19.0,52.0){\small{$\mathcal{S}_{2}$}} \put(19.0,2.5){\small{$\mathcal{S}_{1}$}} \put(72.75,52.0){\small{$\mathcal{S}_{4}$}} \put(72.75,2.5){\small{$\mathcal{S}_{3}$}} \end{overpic}

Figure 9: A decomposition of

\mathscr{M}

into four submanifolds

\mathscr{M}_{1},\ldots,\mathscr{M}_{4}

intersecting along (possibly disconnected) closed surfaces

\mathcal{R}_{i}

Figure 10: An admissible choice of splitting surfaces

\mathcal{S}_{i}

for the

\mathscr{M}_{i}

that is compatible with the trivial ordering

\ell(i)\mapsto i

Figure 11: The faithful fork complex that represents the generalized Heegaard splitting shown in the center (\Creffig:gen-heegaard).

Figure 12: Schematics of a generalized Heegaard splitting (based on figures from [26, Section 2.4]).

Just as compression bodies can be represented by forks, (generalized) Heegaard splittings can be visualized via fork complexes, see \Creffig:heegaard-splitting-boundary,fig:forkcomp (cf. [49, Section 5.1] for details).

Sweep-outs of 3-manifolds

A generalized Heegaard splitting $\mathscr{H}$ of a $3$ -manifold $\mathscr{M}$ induces a sweep-out $f\colon\mathscr{M}\rightarrow\|\mathscr{F}\|$ of $\mathscr{M}$ along any fork complex $\mathscr{F}$ that represents $\mathscr{H}$ (here $\|\mathscr{F}\|$ denotes a drawing, i.e., a geometric realization of the abstract fork complex $\mathscr{F}$ ) by concatenating the corresponding sweep-outs of the compression bodies that comprise $\mathscr{H}$ (cf. \Crefrem:sweep-out-fork). We also refer to a sweep-out $f\colon\mathscr{M}\rightarrow\|\mathscr{F}\|$ by the ensemble $\Sigma=\{\Sigma_{x}:x\in\|\mathscr{F}\|\}$ of its level sets, where $\Sigma_{x}=f^{-1}(x)$ .

The width of a generalized Heegaard splitting

For a generalized Heegaard splitting $\mathscr{H}$ , the surfaces $\mathcal{S}_{i}$ $(i\in I)$ are also called the thick levels, and the lower boundaries $\partial_{-}\mathcal{C}^{(i)}_{1}$ , $\partial_{-}\mathcal{C}^{(i)}_{2}$ are called the thin levels of $\mathscr{H}$ . The width $0pt(\mathscr{H})$ of $\mathscr{H}$ is the sequence obtained by taking a non-increasing ordering of the multiset $\{g(\mathcal{S}_{i}):i\in I\}$ of the genera of the thick levels.

A generalized Heegaard splitting $\mathscr{H}$ of a 3-manifold $\mathscr{M}$ for which $0pt(\mathscr{H})$ is minimal with respect to the lexicographic order ( $<$ ) among all splittings of $\mathscr{M}$ is said to be in thin position.

3.3 Weak reductions

A Heegaard splitting $(\mathcal{C}_{1},\mathcal{C}_{2},\mathcal{S})$ of a connected 3-manifold is said to be weakly reducible [19], if there are essential disks $D_{i}\subset\mathcal{C}_{i}$ $(i=1,2)$ ¹⁰¹⁰10The assumption that $D_{i}$ is essential in the compression body $\mathcal{C}_{i}$ implies that $\partial D_{i}\subset\partial_{+}\mathcal{C}_{i}=\mathcal{S}$ $(i=1,2)$ . with $\partial D_{1}\cap\partial D_{2}=\emptyset$ , see \Creffig:weak-reduction-surface. In this case we also say that the splitting surface $\mathcal{S}$ is weakly reducible. A generalized Heegaard splitting $\mathscr{H}$ is weakly reducible, if at least one of its splitting surfaces is weakly reducible; otherwise $\mathscr{H}$ is called strongly irreducible. Every 3-manifold possesses a strongly irreducible generalized Heegaard splitting and this fact can be exploited in various contexts (e.g., in the proof of \Crefthm:jsj-width). The usefulness of such splittings is mainly due to the following seminal result.

Theorem 3.3 ([49, Lemma 5.2.4], [50, Rule 5]).

Let $\mathscr{H}$ be a strongly irreducible generalized Heegaard splitting. Then every connected component of every thin level of $\mathscr{H}$ is incompressible.

Given a weakly reducible generalized Heegaard splitting $\mathscr{H}$ with a weakly reducible splitting surface¹¹¹¹11For future reference we remind the reader that splitting surfaces, also called thick levels, correspond to grips in the faithful fork complex that represents the generalized Heegaard splitting $\mathscr{H}$ . $\mathcal{S}$ and essential disks $D_{1}$ and $D_{2}$ as above, one can execute a weak reduction at $\mathcal{S}$ . This modification amounts to performing particular cut-and-paste operations on $\mathcal{S}$ guided by $D_{1}$ and $D_{2}$ , and decomposes each of the two compression bodies adjacent to $\mathcal{S}$ into a pair of compression bodies. Importantly, this operation results in another generalized Heegaard splitting $\mathscr{H}^{\prime}$ of the same 3-manifold with $0pt(\mathscr{H}^{\prime})<0pt(\mathscr{H})$ .

We illustrate weak reductions via \Crefex:weak-reduction and refer to [49, Proposition 5.2.3] for further details (notably, Figures 5.8–5.13 therein, but also Lemma 5.2.2, Figures 5.6 and 5.7, and Proposition 5.2.4), including an exhaustive list of instances of weak reductions.¹²¹²12In the open-access version [48] these are Proposition 4.2.3 and Figures 87–92 (as well as Lemma 4.2.2, Figures 85 and 86, and Lemma 4.2.4).

\begin{overpic}[scale={.9}]{weak-reduction-surface} \put(28.25,54.0){\small{$D_{1}$}} \put(25.25,18.5){\small{$\mathcal{S}$}} \put(65.5,21.5){\small{$D_{2}$}} \end{overpic}

Figure 13: Local picture of a portion of a weakly reducible splitting surface

\mathcal{S}

4 The Main Result

In this section we prove Theorem 1.1. The inequalities (1) and (2) are deduced in the same way, thus we only show the proof of (1) in detail, and then explain how it can be adapted to that of (2). First, we specify what we mean by a “sufficiently complicated” JSJ decomposition.

Definition 4.1.

Given $\delta>0$ , the JSJ decomposition of an irreducible $3$ -manifold $\mathscr{M}$ is $\delta$ -complicated, if any incompressible or strongly irreducible Heegaard surface $\mathcal{S}\subset\mathscr{M}$ with genus $g(\mathcal{S})\leq\delta$ can be isotoped to be simultaneously disjoint from all the JSJ tori of $\mathscr{M}$ .

Proof 4.2 (Proof of inequality (1)).

Our goal is to prove that $\operatorname{tw}(\Gamma(\mathscr{D}))\leq 18(\operatorname{tw}(\mathscr{M})+1)$ , where $\Gamma(\mathscr{D})$ is the dual graph of the $\delta$ -complicated JSJ decomposition of the irreducible 3-manifold $\mathscr{M}$ . To this end, we set $\delta=18(\operatorname{tw}(\mathscr{M})+1)$ and fix a triangulation $\mathscr{T}$ of $\mathscr{M}$ , whose dual graph $\Gamma(\mathscr{T})$ has minimal treewidth, i.e., $\operatorname{tw}(\Gamma(\mathscr{T}))=\operatorname{tw}(\mathscr{M})$ . Now, (1) is established in four stages.

{claimproof}

[1. Setup] By invoking the construction in [28, Section 6], from $\mathscr{T}$ we obtain a generalized Heegaard splitting $\mathscr{H}$ of $\mathscr{M}$ together with a sweep-out $f\colon\mathscr{M}\rightarrow\|\mathscr{F}_{\color{gray}\bullet}\|$ along a non-faithful fork complex $\mathscr{F}_{\color{gray}\bullet}$ representing $\mathscr{H}$ . By construction, $\mathscr{F}_{\color{gray}\bullet}$ is a tree with all of its nodes having degree one or three (\Creffig:tree-ghs), moreover all non-degenerate level surfaces $\Sigma_{x}=f^{-1}(x)$ have genus bounded above by $18(\operatorname{tw}(\mathscr{M})+1)$ . Let $\mathscr{F}_{\circ}$ be the faithful fork complex representing $\mathscr{H}$ . Note that $\mathscr{F}_{\circ}$ is obtained from $\mathscr{F}_{\color{gray}\bullet}$ by replacing every non-faithful fork $F\in\mathscr{F}_{\color{gray}\bullet}$ with the collection $\mathscr{C}_{F}$ of faithful forks that accurately represents the (possibly disconnected) compression body $\mathcal{C}$ corresponding to $F$ . The inverse operation, i.e., for each $F\in\mathscr{F}_{\color{gray}\bullet}$ bundling all faithful forks in $\mathscr{C}_{F}$ into $F$ (see \Creffig:faithful-forks), induces a projection map $\pi\colon\|\mathscr{F}_{\circ}\|\rightarrow\|\mathscr{F}_{\color{gray}\bullet}\|$ between the drawings (cf. Figures 15(i)–(ii)). Note that every fork, tine, or grip in $\mathscr{F}_{\color{gray}\bullet}$ corresponds to a collection of the corresponding items in $\mathscr{F}_{\circ}$ and so the projection map is well-defined.

\begin{overpic}[scale={.909091}]{tree-ghs} \put(54.0,10.0){\Large{$\mathscr{F}_{\color{gray}\bullet}$}} \end{overpic}

Figure 14: (i) A. The dual graph

\Gamma(\mathscr{T})

of some triangulation

\mathscr{T}

of a 3-manifold

\mathscr{M}

. B. Low-congestion routing of

\Gamma(\mathscr{T})

along a host tree with marked root arc

r

. C. Drawing of a non-faithful fork complex

\mathscr{F}_{\color{gray}\bullet}

that represents the generalized Heegaard splitting of

\mathscr{M}

induced by the routing of

\Gamma(\mathscr{T})

. The genera of all (possibly disconnected) thick levels

\mathcal{S}_{i}

is bounded above by

18(\operatorname{tw}(\mathscr{M})+1)

. (ii) Color-coded segmentation of

\|\mathscr{F}_{\color{gray}\bullet}\|

in preparation for the next stage of the proof (cf. Figure 15).

{claimproof}

[2. Weak reductions] In case $\mathscr{H}$ is weakly reducible, we repeatedly perform weak reductions until we obtain a strongly irreducible generalized Heegaard splitting $\mathscr{H}^{\prime}$ of $\mathscr{M}$ . Since weak reductions always decrease the width of a generalized Heegaard splitting, this process terminates after finitely many iterations. Throughout, we maintain that the drawings of the associated faithful fork complexes follow $\|\mathscr{F}_{\color{gray}\bullet}\|$ . Let $\mathscr{F}_{\circ}^{\prime}$ be the faithful fork complex representing the final splitting $\mathscr{H}^{\prime}$ , $f^{\prime}\colon\mathscr{M}\rightarrow\|\mathscr{F}_{\circ}^{\prime}\|$ be the sweep-out of $\mathscr{M}$ induced by $\mathscr{H}^{\prime}$ , and $\pi^{\prime}\colon\|\mathscr{F}_{\circ}^{\prime}\|\rightarrow\|\mathscr{F}_{\color{gray}\bullet}\|$ be the associated projection map (\Creffig:thm-proof(iii)). Due to the nature of weak reductions, $18(\operatorname{tw}(\mathscr{M})+1)$ is still an upper bound on the genus of any (possibly disconnected) level surface of $\pi^{\prime}\circ f^{\prime}\colon\mathscr{M}\rightarrow\|\mathscr{F}_{\color{gray}\bullet}\|$ . As $\mathscr{M}$ is irreducible, we may assume that no component of such a level surface is homeomorphic to a sphere (cf. [36, p. 337]). It follows that the number of components of any level set of $\pi^{\prime}\circ f^{\prime}$ is at most $18(\operatorname{tw}(\mathscr{M})+1)$ .

{claimproof}

[3. Perturbation and isotopy] We now apply a level-preserving perturbation $\pi^{\prime}\leadsto\pi^{\prime\prime}$ on $\pi^{\prime}$ , after which each thin level of $\mathscr{H}^{\prime}$ lies in different level sets of $\pi^{\prime\prime}\circ f^{\prime}\colon\mathscr{M}\rightarrow\|\mathscr{F}_{\color{gray}\bullet}\|$ (\Creffig:thm-proof(iv)). Since $\mathscr{H}^{\prime}$ is strongly irreducible, its thick levels are strongly irreducible (by definition), and its thin levels are incompressible (by \Crefthm:scharlemann-thompson). Moreover, all these surfaces have genera at most $18(\operatorname{tw}(\mathscr{M})+1)$ . Hence, as the JSJ decomposition of $\mathscr{M}$ is assumed to be $\delta$ -complicated with $\delta=18(\operatorname{tw}(\mathscr{M})+1)$ , we may isotope all JSJ tori to be disjoint from all the thick and thin levels of $\mathscr{H}^{\prime}$ . Then, by invoking [5, Corollary 4.5] we can isotope each JSJ torus of $\mathscr{M}$ to coincide with a component of some thin level of $\mathscr{H}^{\prime}$ (\Creffig:thm-proof(v)). As a consequence, every compression body of the splitting $\mathscr{H}^{\prime}$ is contained in a unique JSJ piece of $\mathscr{M}$ .

{claimproof}

[4. The tree decomposition of $\Gamma(\mathscr{D})$ ] First note that every level set $(\pi^{\prime\prime}\circ f^{\prime})^{-1}(x)$ is incident to at most $18(\operatorname{tw}(\mathscr{M})+1)+1=18\operatorname{tw}(\mathscr{M})+19$ JSJ pieces of $\mathscr{M}$ . The ‘plus one’ appears, because if $(\pi^{\prime\prime}\circ f^{\prime})^{-1}(x)$ contains a JSJ torus, then this torus is incident to two JSJ pieces of $\mathscr{M}$ . Also note that, because of the perturbation performed in the previous stage, each level set $(\pi^{\prime\prime}\circ f^{\prime})^{-1}(x)$ can contain at most one JSJ torus of $\mathscr{M}$ .

We now construct a tree decomposition $(\mathscr{X},T)$ of $\Gamma(\mathscr{D})$ of width $18(\operatorname{tw}(\mathscr{M})+1)$ . Eventually, $T$ will be a subdivision of $\mathscr{F}_{\color{gray}\bullet}$ (which is a tree) with nodes corresponding to the bags in $\mathscr{X}$ , which we now describe. By [28, Section 6 (p. 86)], each leaf $l$ of $\mathscr{F}_{\color{gray}\bullet}$ corresponds to a spine of a handlebody $\mathcal{H}_{l}$ . We define a bag that contains the unique node of $\Gamma(\mathscr{D})$ associated with the JSJ piece containing $\mathcal{H}_{l}$ . As we sweep through $\|\mathscr{F}_{\color{gray}\bullet}\|$ (cf. the arrows on \Creffig:tree-ghs(2)), whenever we pass through a point $x\in\|\mathscr{F}_{\color{gray}\bullet}\|$ such that the level set $(\pi^{\prime\prime})^{-1}(x)$ contains a tine of $\|\mathscr{F}_{\circ}^{\prime}\|$ , one of four possible events may occur (illustrated in \Creffig:thm-proof(v)–(vi)): 1. A new JSJ piece appears. In this case we take a copy of the previous bag, and add the corresponding node of $\Gamma(\mathscr{D})$ into the bag. 2. A JSJ piece disappears. Then we delete the corresponding node of $\Gamma(\mathscr{D})$ from a copy of the previous bag. 3. Both previous kinds of events happen simultaneously. In this case we introduce two new bags. The first to introduce the new JSJ piece, the second to delete the old one. 4. If neither a new JSJ piece is introduced, nor an old one is left behind, we do nothing. Whenever we arrive at a merging point in the sweep-out (i.e., a degree-three node of $\|\mathscr{F}_{\color{gray}\bullet}\|$ ), we introduce a new bag, which is the union of the two previous bags. Note that the two previous bags do not necessarily need to be disjoint.

It remains to verify that $(\mathscr{X},T)$ is, indeed, a tree decomposition of $\Gamma(\mathscr{D})$ of width at most $18\operatorname{tw}(\mathscr{M})+18$ . Node coverage: Every node of $\Gamma(\mathscr{D})$ must be considered at least once, since we sweep through the entirety of $\|\mathscr{F}_{\color{gray}\bullet}\|$ . Arc coverage: we must ensure that all pairs of nodes of $\Gamma(\mathscr{D})$ with their JSJ pieces meeting at a tine are contained in some bag. This is always the case for \colorlipicsGray1, because a new JSJ piece appears while all other JSJ pieces are still in the bag. It is also the case for \colorlipicsGray2 because a JSJ piece disappears but the previous bag contained all the pieces. In \colorlipicsGray3 a new JSJ piece appears and at the same time another JSJ piece disappears. However, in this case we first introduce the new piece, thus making sure that adjacent JSJ pieces always occur in at least one bag. Sub-tree property: This follows from the fact that a JSJ piece, once removed from all bags, must be contained in the part of $\|\mathscr{F}_{\color{gray}\bullet}\|$ that was already swept. Now, every JSJ piece incident to a given level set $(\pi^{\prime\prime}\circ f^{\prime})^{-1}(x)$ of the sweep-out must contribute a positive number to its genus. Hence, it follows that every bag can contain at most $18\operatorname{tw}(\mathscr{M})+19$ elements (with equality only possible where a tine simultaneously introduces and forgets a JSJ piece). This proves inequality (1).

Proof 4.3 (Proof of inequality (2)).

We start with the results from [28, Section 5] yielding a fork-complex $\mathscr{F}_{\color{gray}\bullet}$ whose underlying space $\|\mathscr{F}_{\color{gray}\bullet}\|$ is a path, and the genus of the level sets of the associated sweep-out is bounded above by $4(3\operatorname{pw}(\mathscr{M})+1)$ . Setting $\delta=4(3\operatorname{pw}(\mathscr{M})+1)$ , the remainder of the proof is analogous with the proof of inequality (1).

5 An Algorithmic Construction

Here we establish \Crefthm:construction that paves the way to the applications in \Crefsec:appl. In what follows, $\Delta$ denotes an arbitrary, but fixed, positive integer. Let $G=(V,E)$ be a graph with $|V|=n$ and maximum degree $\Delta$ . \Crefthm:construction asserts that, in $\operatorname{poly}(n)$ time one can construct a triangulation $\mathscr{T}_{G}$ of a closed, irreducible 3-manifold $\mathscr{M}_{G}$ , such that the dual graph $\Gamma(\mathscr{D})$ of its JSJ decomposition $\mathscr{D}$ equals $G$ , moreover, the pathwidth (resp. treewidth) of $G$ determines the pathwidth (resp. treewidth) of $\mathscr{M}_{G}$ up to a constant factor.

Our proof of \Crefthm:construction rests on a synthesis of work by Lackenby [37] and by Bachman, Derby-Talbot and Sedgwick [6]. In [37, Section 3] it is shown that the homeomorphism problem for closed 3-manifolds is at least as hard as the graph isomorphism problem. The proof relies on a simple construction that, given a graph $G$ , produces a closed, orientable, triangulated 3-manifold whose JSJ decomposition $\mathscr{D}$ satisfies $\Gamma(\mathscr{D})=G$ . This gives the blueprint for our construction as well. In particular, we use the same building blocks that are described in [37, p. 591]. However, as opposed to Lackenby, we paste together these building blocks via high-distance torus gluings akin to the construction presented in [6, Section 4]. This ensures that we can apply \Crefthm:jsj-width for the resulting 3-manifold $\mathscr{M}_{G}$ and deduce the right-hand-side inequalities of \colorlipicsGray3a and \colorlipicsGray3b. The left-hand-side inequalities are shown by inspecting $\mathscr{T}_{G}$ . We now elaborate on the ingredients of the proof of \Crefthm:construction.

The building blocks

We first recall the definition of the building blocks from [37, p. 591]. Let $k\in\mathbb{N}$ be a positive integer. Consider the 2-dimensional torus $\mathbb{T}^{2}=\mathbb{S}^{1}\times\mathbb{S}^{1}$ , and let $\mathbb{T}^{2}_{k}$ denote the compact surface obtained from $\mathbb{T}^{2}$ by the removal of $k$ pairwise disjoint open disks. We define $\mathscr{N}(k)=\mathbb{T}^{2}_{k}\times\mathbb{S}^{1}$ . Note that the boundary $\partial\mathscr{N}(k)$ of $\mathscr{N}(k)$ consists of $k$ tori, which will be the gluing sites. See \Creffig:building-block for the example of $\mathscr{N}(3)$ .

We choose a triangulation $\mathscr{T}(k)$ for $\mathscr{N}(k)$ that induces the minimal 2-triangle triangulation of the torus (cf. \Creffig:torus-trg) at each boundary component. Note that $\mathscr{T}(k)$ can be constructed from $O(k)$ tetrahedra. An explicit description of $\mathscr{T}(k)$ is given in \Crefapp:trg.

\nolinenumbers

\begin{overpic}[scale={0.75}]{torus-3-holes} \put(-47.0,37.0){\large{$\mathscr{N}(3)=$}} \put(106.0,37.0){\large{$\times~{}\mathbb{S}^{1}$}} \end{overpic}\captionof

figureIllustration of $\mathscr{N}(3)$ .

\begin{overpic}[scale={0.75}]{torus-trg} \end{overpic}\captionof

figure\nolinenumbersMinimal triangulation of the torus $\mathbb{T}^{2}$ .

Overview of the construction of $\boldsymbol{\mathscr{M}_{G}}$

We now give a high-level overview of constructing $\mathscr{M}_{G}$ from the above building blocks. Given a graph $G=(V,E)$ , for each node $v\in V$ we pick a block $\mathscr{N}_{v}\cong\mathscr{N}(d_{v})$ , where $d_{v}$ denotes the degree of $v$ . Next, for each arc $e=\{u,v\}\in E$ , we pick a homeomorphism $\phi_{e}\colon\mathbb{T}^{2}\rightarrow\mathbb{T}^{2}$ of sufficiently high distance (we discuss this notion below) and use it to glue together a boundary torus of $\mathscr{N}_{u}$ with one of $\mathscr{N}_{v}$ . After performing all of these gluings, we readily obtain the 3-manifold $\mathscr{M}_{G}$ (cf. \Creffig:schematic-construction(i)–(ii)).

Claim 1 (name=Based on [37, p. 591], label=claim:jsj).

The JSJ decomposition $\mathscr{D}$ of $\mathscr{M}_{G}$ satisfies $\Gamma(\mathscr{D})=G$ .

For a proof of \Crefclaim:jsj we refer to \Crefapp:jsj.

\begin{overpic}[scale={0.45128205128}]{schematic-var} \put(30.0,24.5){\small{high-distance}} \put(30.0,21.0){\small{torus gluings}} \put(51.0,40.5){\small{layered}} \put(51.0,37.0){\small{triangulations}} \put(14.5,-4.0){\large{$\mathscr{M}_{G}$}} \put(74.0,-4.0){\large{$\Gamma(\mathscr{T}_{G})$}} \put(-1.5,19.0){\small{$\mathscr{N}(3)\cong\mathscr{N}_{v}$}} \put(-1.5,28.0){\small{$\mathscr{N}(1)\cong\mathscr{N}_{u}$}} \put(-1.0,1.0){\small{$\mathscr{N}_{w}$}} \put(28.75,1.0){\small{$\mathscr{N}_{z}\cong\mathscr{N}(2)$}} \put(74.0,54.0){\scalebox{0.7}{{$\Gamma(\mathscr{T}(1))$}}} \put(73.0,23.75){\small{$\Gamma(\mathscr{T}(3))$}} \put(57.5,5.45){\scalebox{0.8}{{$\Gamma(\mathscr{T}(2))$}}} \put(89.8,5.45){\scalebox{0.8}{{$\Gamma(\mathscr{T}(2))$}}} \put(20.0,52.0){\large{$G$}} \put(12.5,58.0){\small{$u$}} \put(12.5,48.0){\small{$v$}} \put(3.5,38.5){\small{$w$}} \put(27.0,38.5){\small{$z$}} \put(-8.0,50.0){\small{(i)}} \put(-8.0,15.0){\small{(ii)}} \put(92.0,50.0){\small{(iii)}} \end{overpic}

Figure 16: Schematic overview of the construction underlying \Crefthm:construction.

High-distance torus gluings

As already mentioned, to ensure that we can apply \Crefthm:jsj-width to $\mathscr{M}_{G}$ , we use torus homeomorphisms of “sufficiently high distance” to glue the building blocks together. This notion of distance, which is defined through the Farey distance, is somewhat technical. Thus, we refer to [6, Section 4.1 and Appendix] for details, and rather recall a crucial result that makes the usefulness of distance in the current context apparent.

Theorem 5.1 ([6, Appendix], [4, Theorem 5.4]¹³¹³13The notation and the statement of \Crefthm:distance have been adapted to match the present context.).

There exists a computable constant $K$ , depending only on the homeomorphism types of the blocks, so that if any set of blocks are glued with maps of distance at least $K\delta$ along their torus boundary components to form a closed $3$ -manifold $\mathscr{M}$ , then the JSJ decomposition of $\mathscr{M}$ is $\delta$ -complicated (cf. \Crefdef:complicated-jsj).

Triangulating the gluing maps

We have already discussed that the block $\mathscr{N}(k)$ admits a triangulation $\mathscr{T}(k)$ with $O(k)$ tetrahedra, where $\mathscr{T}(k)$ induces a minimal, 1-vertex triangulation at each torus boundary of $\mathscr{N}(k)$ . It is shown in [6, Section 4.2] that the gluings beading these blocks together can be realized as layered triangulations [29]. These triangulations manifest as “daisy chains” in the dual graph $\Gamma(\mathscr{T}_{G})$ of the final triangulation $\mathscr{T}_{G}$ , see \Creffig:schematic-construction(iii).

Lemma 5.2 ([6, Lemma 4.6]).

There exist torus gluings with distance at least $D$ , that can be realized as layered triangulations using $2D$ tetrahedra.

Claim 2.

There exist universal constants $c,c^{\prime}>0$ such that

\displaystyle(c/\Delta)\operatorname{tw}(\mathscr{M}_{G})\leq\operatorname{tw}(G)\quad\text{and}\quad(c^{\prime}/\Delta)\operatorname{pw}(\mathscr{M}_{G})\leq\operatorname{pw}(G).

{claimproof}

Since every node of $G$ has degree at most $\Delta$ , the construction of $\mathscr{M}_{G}$ only uses building blocks homeomorphic to $\mathscr{N}(1),\ldots,\mathscr{N}(\Delta)$ . Hence, for each $v\in V$ the triangulation $\mathscr{T}(d_{v})$ of the block $\mathscr{N}_{v}$ contains $O(\Delta)$ tetrahedra. This, together with the above discussion on triangulating the gluing maps implies that (upon ignoring multi-arcs and loop arcs, which are anyway not “sensed” by treewidth or pathwidth), the dual graph $\Gamma(\mathscr{T}_{G})$ is obtained from $G$ by 1. replacing each node $v\in V$ with a copy of the graph $\Gamma(\mathscr{T}(d_{v}))$ that contains $O(\Delta)$ nodes, and by 2. possibly subdividing each arc $e\in E$ several times.

Now, the first operation increases the treewidth (resp. pathwidth) at most by a factor of $O(\Delta)$ , while the arc-subdivisions keep these parameters basically the same, cf. \Creflem:subdiv-pw. Hence $\operatorname{tw}(\Gamma(\mathscr{T}_{G}))\leq O(\Delta\operatorname{tw}(G))$ and $\operatorname{pw}(\Gamma(\mathscr{T}_{G}))\leq O(\Delta\operatorname{pw}(G))$ , and the claim follows.

Lemma 5.3 (Folklore, cf. [9, Lemma A. 1]).

Let $G=(V,E)$ be a graph. If $G^{\prime}$ is a graph obtained from $G$ by subdividing a set $F\subseteq E$ of arcs an arbitrary number of times. Then

\displaystyle\operatorname{pw}(G^{\prime})\leq\operatorname{pw}(G)+2\qquad\text{and}\qquad\operatorname{tw}(G^{\prime})\leq\max\{\operatorname{tw}(G),3\}.

Proof 5.4 (Finishing the proof of \Crefthm:construction).

We have already shown \colorlipicsGray2 (\Crefclaim:jsj) and the left-hand-sides of the inequalities \colorlipicsGray3a and \colorlipicsGray3b (\Crefclaim:lhs-inequalities). To prove the remaining parts of \Crefthm:construction, let $\delta=\max\{18(\operatorname{tw}(G)+1),4(3\operatorname{pw}(G)+1)\}=O(\operatorname{pw}(G))$ . By \Crefthm:distance, there is a computable constant $K_{\Delta}$ depending only on $\mathscr{N}(1),\ldots,\mathscr{N}(\Delta)$ and hence only on $\Delta$ , so that if we glue together the blocks via maps of distance at least $K_{\Delta}\delta$ , then the JSJ decomposition of $\mathscr{M}_{G}$ is $\delta$ -complicated. By \Creflem:layering, each such gluing map can be realized as a layered triangulation consisting of $2K_{\Delta}\delta$ tetrahedra. Since $G$ has at most $\Delta n/2$ arcs, these layered triangulations contain at most $2K_{\Delta}\delta\Delta n/2=\Delta K_{\Delta}\delta n=O(\Delta K_{\Delta}\operatorname{pw}(G)\cdot n)=O_{\Delta}(\operatorname{pw}(G)\cdot n)$ tetrahedra altogether. Since the triangulated blocks $\mathscr{T}(d_{v})$ contain $O(\Delta\cdot n)$ tetrahedra in total, the triangulation $\mathscr{T}_{G}$ of the manifold $\mathscr{M}_{G}$ can be built from $O_{\Delta}(\operatorname{pw}(G)\cdot n)\leq O_{\Delta}(n^{2})$ tetrahedra. Last, as it follows from [6, Section 4], the construction can be executed in quadratic time.

6 Applications

Corollary 6.1.

There exist $3$ -manifolds $(\mathscr{M}_{h})_{h\in\mathbb{N}}$ with $\operatorname{tw}(\mathscr{M}_{h})\leq 2$ and $\operatorname{pw}(\mathscr{M}_{h})\overset{h\to\infty}{\longrightarrow}\infty$ .

Corollary 6.2.

There exist Haken $3$ -manifolds $(\mathscr{N}_{k})_{k\in\mathbb{N}}$ with $\operatorname{tw}(\mathscr{N}_{k})\overset{k\to\infty}{\longrightarrow}\infty$ .

Proof 6.3 (Proof of \Crefcor:unbounded-pathwidth,cor:unbounded-treewidth).

Using Theorem 1.2, the construction of bounded-treewidth (Haken) 3-manifolds with arbitrarily large pathwidth follows by taking $\mathscr{M}_{h}=\mathscr{M}_{T_{h}}$ (with the notation of \Crefthm:construction), where $T_{h}$ is the complete binary tree of height $h$ . The construction of Haken 3-manifolds of arbitrary large treewidth is deduced by setting $\mathscr{N}_{k}=\mathscr{M}_{\operatorname{Grid}(k)}$ , where $\operatorname{Grid}(k)$ denotes the $k\times k$ grid graph. See \Creffig:pw-tw. Obtained as JSJ decompositions, where the JSJ tori are two-sided, incompressible surfaces, all of these manifolds are Haken.

\begin{overpic}[scale={0.8205128205}]{pw-tw_examples-2} \put(56.5,19.25){\footnotesize{$\operatorname{Grid}(5)$}} \end{overpic}

Figure 17: (i) The complete binary tree

T_{h}

of height

h

has pathwidth

\lceil h/2\rceil

, cf. [11, Theorem 67]. (ii) The

k\times k

grid graph is known to have pathwidth and treewidth both equal to

k

Corollary 6.4.

Approximating the treewidth (resp. pathwidth) of closed, orientable $3$ -manifolds up to a constant factor is at least as hard as giving a constant-factor approximation of the treewidth (resp. pathwidth) of bounded-degree graphs.

Proof 6.5.

The argument for treewidth and pathwidth is the same. Given a graph $G$ with maximum vertex degree $\Delta$ , we use the polynomial-time procedure from \Crefthm:construction to build a $3$ -manifold $\mathscr{M}$ with $\operatorname{tw}(\mathscr{M})$ within a constant factor of $\operatorname{tw}(G)$ . An oracle for a constant-factor approximation of $\operatorname{tw}(\mathscr{M})$ hence gives us a constant-factor approximation of $\operatorname{tw}(G)$ as well.

Remark 6.6.

Computing a constant-factor approximation of treewidth (resp. pathwidth) for arbitrary graphs is known to be conditionally NP-hard under the Small Set Expansion Hypothesis [46, 55, 56]. For proving \Crefcor:hardness-treewidth, however, we rely on the assumption that the graph has bounded degree. Thus the conditional hardness of approximating the treewidth (resp. pathwidth) of a $3$ -manifold does not directly follow. Establishing such a hardness result would add to the growing, but still relatively short list of algorithmic problems in low-dimensional topology that are known to be (conditionally) hard, cf. [2, 6, 21, 33, 37].

7 Discussion and Open Problems

We have demonstrated that $3$ -manifolds with JSJ decompositions with dual graphs of large treewidth (resp. pathwidth) and “sufficiently complicated” gluing maps cannot admit triangulations of low treewidth (resp. pathwidth). This provides a technique to construct a wealth of families of $3$ -manifolds with unbounded tree- or pathwidth that hopefully will prove to be useful for future research in the field.

One obvious limitation of our construction is a seemingly heavy restriction on the JSJ gluing maps in order to deduce a connection between the treewidth of a $3$ -manifold and that of the dual graph of its JSJ decomposition. Hence, a natural question to ask is, how much this restriction on gluing maps may be relaxed while still allowing meaningful structural results about treewidth. In particular, we have the following question.

Question 7.1.

Given a $3$ -manifold $\mathscr{M}$ with JSJ decomposition $\mathscr{D}$ and no restrictions on its JSJ gluings. Is there a lower bound for $\operatorname{tw}(\mathscr{M})$ in terms of $\operatorname{tw}(\Gamma(\mathscr{D}))$ ?

Note that the assumption that we are considering the JSJ decomposition of $\mathscr{M}$ is necessary: Consider a graph $G=(V,E)$ and a collection of $3$ -manifolds $\{\mathscr{M}_{v}\}_{v\in V}$ , where $\mathscr{M}_{v}$ has $\deg(v)$ torus boundary components. Assume that we glue the manifolds $\mathscr{M}_{v}$ along the arcs of $G$ to obtain a closed $3$ -manifold $\mathscr{M}$ . Without restrictions on how these pieces are glued together, this cannot result in a lower bound $\operatorname{tw}(\mathscr{M})$ in terms of $\operatorname{tw}(G)$ : we can construct Seifert fibered spaces $\mathscr{M}$ in this way, even if $G=(V,E)$ is the complete graph with $|V|$ arbitrarily large. At the same time, Seifert fibered spaces have constant treewidth, see [27].

Question 7.2.

What is the complexity of computing the treewidth of a $3$ -manifold?

We believe that this should be at least as hard as computing the treewidth of a graph.

References

[1] I. Agol. Small 3-manifolds of large genus. Geom. Dedicata, 102:53–64, 2003. \hrefhttps://doi.org/10.1023/B:GEOM.0000006584.85248.c5 \pathdoi:10.1023/B:GEOM.0000006584.85248.c5.
[2] I. Agol, J. Hass, and W. Thurston. The computational complexity of knot genus and spanning area. Trans. Am. Math. Soc., 358(9):3821–3850, 2006. \hrefhttps://doi.org/10.1090/S0002-9947-05-03919-X \pathdoi:10.1090/S0002-9947-05-03919-X.
[3] M. A. Armstrong. Basic topology. Undergrad. Texts Math. Springer-Verlag, New York-Berlin, 1983. Corrected reprint of the 1979 original. \hrefhttps://doi.org/10.1007/978-1-4757-1793-8 \pathdoi:10.1007/978-1-4757-1793-8.
[4] D. Bachman. Stabilizing and destabilizing Heegaard splittings of sufficiently complicated 3-manifolds. Math. Ann., 355(2):697–728, 2013. \hrefhttps://doi.org/10.1007/s00208-012-0802-4 \pathdoi:10.1007/s00208-012-0802-4.
[5] D. Bachman, R. Derby-Talbot, and E. Sedgwick. Heegaard structure respects complicated JSJ decompositions. Math. Ann., 365(3-4):1137–1154, 2016. \hrefhttps://doi.org/10.1007/s00208-015-1314-9 \pathdoi:10.1007/s00208-015-1314-9.
[6] D. Bachman, R. Derby-Talbot, and E. Sedgwick. Computing Heegaard genus is NP-hard. In A Journey Through Discrete Mathematics: A Tribute to Jiří Matoušek, pages 59–87. Springer, Cham, 2017. \hrefhttps://doi.org/10.1007/978-3-319-44479-6_3 \pathdoi:10.1007/978-3-319-44479-6_3.
[7] D. Bachman, S. Schleimer, and E. Sedgwick. Sweepouts of amalgamated 3-manifolds. Algebr. Geom. Topol., 6:171–194, 2006. \hrefhttps://doi.org/10.2140/agt.2006.6.171 \pathdoi:10.2140/agt.2006.6.171.
[8] B. Bagchi, B. A. Burton, B. Datta, N. Singh, and J. Spreer. Efficient algorithms to decide tightness. In 32nd Int. Symp. Comput. Geom. (SoCG 2016), volume 51 of LIPIcs. Leibniz Int. Proc. Inf., pages 12:1–12:15. Schloss Dagstuhl–Leibniz-Zent. Inf., 2016. \hrefhttps://doi.org/10.4230/LIPIcs.SoCG.2016.12 \pathdoi:10.4230/LIPIcs.SoCG.2016.12.
[9] R. Belmonte, T. Hanaka, M. Kanzaki, M. Kiyomi, Y. Kobayashi, Y. Kobayashi, M. Lampis, H. Ono, and Y. Otachi. Parameterized complexity of $(A,\ell)$ -path packing. Algorithmica, 84(4):871–895, 2022. \hrefhttps://doi.org/10.1007/s00453-021-00875-y \pathdoi:10.1007/s00453-021-00875-y.
[10] R. H. Bing. An alternative proof that $3$ -manifolds can be triangulated. Ann. Math. (2), 69:37–65, 1959. \hrefhttps://doi.org/10.2307/1970092 \pathdoi:10.2307/1970092.
[11] H. L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci., 209(1–2):1–45, 1998. \hrefhttps://doi.org/10.1016/S0304-3975(97)00228-4 \pathdoi:10.1016/S0304-3975(97)00228-4.
[12] 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. \hrefhttps://doi.org/10.1090/conm/597/11877 \pathdoi:10.1090/conm/597/11877.
[13] B. A. Burton, R. Budney, W. Pettersson, et al. Regina: Software for low-dimensional topology, 1999–2022. Version 7.2. URL: \urlhttps://regina-normal.github.io.
[14] B. A. Burton and R. G. Downey. Courcelle’s theorem for triangulations. J. Comb. Theory, Ser. A, 146:264–294, 2017. \hrefhttps://doi.org/10.1016/j.jcta.2016.10.001 \pathdoi:10.1016/j.jcta.2016.10.001.
[15] 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. \hrefhttps://doi.org/10.1145/2738034 \pathdoi:10.1145/2738034.
[16] 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. \hrefhttps://doi.org/10.1007/s41468-018-0016-2 \pathdoi:10.1007/s41468-018-0016-2.
[17] B. A. Burton and W. Pettersson. Fixed parameter tractable algorithms in combinatorial topology. In Proc. 20th Int. Conf. Comput. Comb. (COCOON 2014), pages 300–311, 2014. \hrefhttps://doi.org/10.1007/978-3-319-08783-2_26 \pathdoi:10.1007/978-3-319-08783-2_26.
[18] 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. \hrefhttps://doi.org/10.1137/1.9781611973105.13 \pathdoi:10.1137/1.9781611973105.13.
[19] A. J. Casson and C. McA. Gordon. Reducing Heegaard splittings. Topology Appl., 27(3):275–283, 1987. \hrefhttps://doi.org/10.1016/0166-8641(87)90092-7 \pathdoi:10.1016/0166-8641(87)90092-7.
[20] H. S. M. Coxeter. Regular honeycombs in hyperbolic space. In Proc. Int. Congr. Math., Amsterdam, The Netherlands, September 2–9, 1954, volume 3, pages 155–169. Erven P. Noordhoff; North-Holland, 1956. Available at \urlhttps://www.mathunion.org/fileadmin/ICM/Proceedings/ICM1954.3/ICM1954.3.ocr.pdf (accessed: March 12, 2023).
[21] A. de Mesmay, Y. Rieck, E. Sedgwick, and M. Tancer. The unbearable hardness of unknotting. Adv. Math., 381:Paper No. 107648, 36, 2021. \hrefhttps://doi.org/10.1016/j.aim.2021.107648 \pathdoi:10.1016/j.aim.2021.107648.
[22] Henri Paul de Saint-Gervais. Uniformization of Riemann surfaces. Revisiting a hundred-year-old theorem. Translated from the French by R. G. Burns. Herit. Eur. Math. Eur. Math. Soc. (EMS), Zürich, 2016. \hrefhttps://doi.org/10.4171/145 \pathdoi:10.4171/145.
[23] A. Hatcher. Notes on basic 3-manifold topology. Available at \urlhttps://pi.math.cornell.edu/ hatcher/3M/3Mfds.pdf (accessed: February 18, 2023).
[24] P. Heegaard. Sur l’”Analysis situs”. Bull. Soc. Math. France, 44:161–242, 1916. \hrefhttps://doi.org/10.24033/bsmf.968 \pathdoi:10.24033/bsmf.968.
[25] K. Huszár. Combinatorial width parameters for $3$ -dimensonal manifolds. PhD thesis, IST Austria, June 2020. \hrefhttps://doi.org/10.15479/AT:ISTA:8032 \pathdoi:10.15479/AT:ISTA:8032.
[26] K. Huszár. On the pathwidth of hyperbolic 3-manifolds. Comput. Geom. Topol., 1(1):1–19, 2022. \hrefhttps://doi.org/10.57717/cgt.v1i1.4 \pathdoi:10.57717/cgt.v1i1.4.
[27] 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. \hrefhttps://doi.org/10.4230/LIPIcs.SoCG.2019.44 \pathdoi:10.4230/LIPIcs.SoCG.2019.44.
[28] K. Huszár, J. Spreer, and U. Wagner. On the treewidth of triangulated 3-manifolds. J. Comput. Geom., 10(2):70–98, 2019. \hrefhttps://doi.org/10.20382/jogc.v10i2a5 \pathdoi:10.20382/jogc.v10i2a5.
[29] W. Jaco and J. H. Rubinstein. Layered-triangulations of 3-manifolds, 2006. 97 pages, 32 figures. \hrefhttp://arxiv.org/abs/math/0603601 \patharXiv:math/0603601.
[30] W. Jaco and P. B. Shalen. A new decomposition theorem for irreducible sufficiently-large $3$ -manifolds. In Algebraic and Geometric Topology, volume 32, part 2 of Proc. Sympos. Pure Math., pages 71–84. Am. Math. Soc., Providence, RI, 1978. \hrefhttps://doi.org/10.1090/pspum/032.2/520524 \pathdoi:10.1090/pspum/032.2/520524.
[31] W. H. Jaco and P. B. Shalen. Seifert fibered spaces in $3$ -manifolds. Mem. Am. Math. Soc., 21(220):viii+192, 1979. \hrefhttps://doi.org/10.1090/memo/0220 \pathdoi:10.1090/memo/0220.
[32] K. Johannson. Homotopy equivalences of $3$ -manifolds with boundaries, volume 761 of Lect. Notes Math. Springer, Berlin, 1979. \hrefhttps://doi.org/10.1007/BFb0085406 \pathdoi:10.1007/BFb0085406.
[33] D. Koenig and A. Tsvietkova. NP-hard problems naturally arising in knot theory. Trans. Am. Math. Soc. Ser. B, 8:420–441, 2021. \hrefhttps://doi.org/10.1090/btran/71 \pathdoi:10.1090/btran/71.
[34] G. Kuperberg. Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization. Pacific J. Math., 301(1):189–241, 2019. \hrefhttps://doi.org/10.2140/pjm.2019.301.189 \pathdoi:10.2140/pjm.2019.301.189.
[35] M. Lackenby. The Heegaard genus of amalgamated 3-manifolds. Geom. Dedicata, 109:139–145, 2004. \hrefhttps://doi.org/10.1007/s10711-004-6553-y \pathdoi:10.1007/s10711-004-6553-y.
[36] M. Lackenby. Heegaard splittings, the virtually Haken conjecture and property $(\tau)$ . Invent. Math., 164(2):317–359, 2006. \hrefhttps://doi.org/10.1007/s00222-005-0480-x \pathdoi:10.1007/s00222-005-0480-x.
[37] M. Lackenby. Some conditionally hard problems on links and 3-manifolds. Discrete Comput. Geom., 58(3):580–595, 2017. \hrefhttps://doi.org/10.1007/s00454-017-9905-8 \pathdoi:10.1007/s00454-017-9905-8.
[38] 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, 2020. \hrefhttps://doi.org/10.4310/SDG.2020.v25.n1.a5 \pathdoi:10.4310/SDG.2020.v25.n1.a5.
[39] Tao Li. Heegaard surfaces and the distance of amalgamation. Geom. Topol., 14(4):1871–1919, 2010. \hrefhttps://doi.org/10.2140/gt.2010.14.1871 \pathdoi:10.2140/gt.2010.14.1871.
[40] C. Manolescu. Lectures on the triangulation conjecture. In Proc. 22nd Gökova Geom.-Topol. Conf. (GGT 2015), pages 1–38. Int. Press Boston, 2016. URL: \urlhttps://gokovagt.org/proceedings/2015/manolescu.html.
[41] C. Maria and J. Purcell. Treewidth, crushing and hyperbolic volume. Algebr. Geom. Topol., 19(5):2625–2652, 2019. \hrefhttps://doi.org/10.2140/agt.2019.19.2625 \pathdoi:10.2140/agt.2019.19.2625.
[42] A. Markov. The insolubility of the problem of homeomorphy (in Russian). Dokl. Akad. Nauk SSSR, 121:218–220, 1958.
[43] E. E. Moise. Affine structures in $3$ -manifolds. V. The triangulation theorem and Hauptvermutung. Ann. Math. (2), 56:96–114, 1952. \hrefhttps://doi.org/10.2307/1969769 \pathdoi:10.2307/1969769.
[44] P. Orlik, E. Vogt, and H. Zieschang. Zur Topologie gefaserter dreidimensionaler Mannigfaltigkeiten. Topology, 6:49–64, 1967. \hrefhttps://doi.org/10.1016/0040-9383(67)90013-4 \pathdoi:10.1016/0040-9383(67)90013-4.
[45] B. Poonen. Undecidable problems: a sampler. In Interpreting Gödel, pages 211–241. Cambridge Univ. Press, 2014. \hrefhttps://doi.org/10.1017/CBO9780511756306.015 \pathdoi:10.1017/CBO9780511756306.015.
[46] P. Raghavendra and D. Steurer. Graph expansion and the unique games conjecture. In Proc. 2010 ACM Int. Symp. Theor. Comput. (STOC’10), pages 755–764. ACM, New York, 2010.
[47] M. Scharlemann and J. Schultens. Comparing Heegaard and JSJ structures of orientable 3-manifolds. Trans. Am. Math. Soc., 353(2):557–584, 2001. \hrefhttps://doi.org/10.1090/S0002-9947-00-02654-4 \pathdoi:10.1090/S0002-9947-00-02654-4.
[48] M. Scharlemann, J. Schultens, and T. Saito. Lecture notes on generalized Heegaard splittings, 2005. Open-access version of [49] with slightly different structure. \hrefhttp://arxiv.org/abs/math/0504167 \patharXiv:math/0504167.
[49] M. Scharlemann, J. Schultens, and T. Saito. Lecture Notes on Generalized Heegaard Splittings. World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2016. \hrefhttps://doi.org/10.1142/10019 \pathdoi:10.1142/10019.
[50] M. Scharlemann and A. Thompson. Thin position for $3$ -manifolds. In Geometric topology (Haifa, 1992), volume 164 of Contemp. Math., pages 231–238. Am. Math. Soc., Providence, RI, 1994. \hrefhttps://doi.org/10.1090/conm/164/01596 \pathdoi:10.1090/conm/164/01596.
[51] J. Schultens. Introduction to $3$ -Manifolds, volume 151 of Grad. Stud. Math. Am. Math. Soc., Providence, RI, 2014. \hrefhttps://doi.org/10.1090/gsm/151 \pathdoi:10.1090/gsm/151.
[52] J. Schultens and R. Weidmann. Destabilizing amalgamated Heegaard splittings. In Workshop on Heegaard Splittings, volume 12 of Geom. Topol. Monogr., pages 319–334. Geom. Topol. Publ., Coventry, 2007. \hrefhttps://doi.org/10.2140/gtm.2007.12.319 \pathdoi:10.2140/gtm.2007.12.319.
[53] P. Scott and H. Short. The homeomorphism problem for closed 3-manifolds. Algebr. Geom. Topol., 14(4):2431–2444, 2014. \hrefhttps://doi.org/10.2140/agt.2014.14.2431 \pathdoi:10.2140/agt.2014.14.2431.
[54] F. Waldhausen. Eine Klasse von $3$ -dimensionalen Mannigfaltigkeiten. I, II. Invent. Math., 3:308–333; ibid. 4:87–117, 1967. URL: \urlhttps://eudml.org/doc/141878 and \urlhttps://eudml.org/doc/141884. \hrefhttps://doi.org/10.1007/BF01402956 \pathdoi:10.1007/BF01402956.
[55] Y. Wu, P. Austrin, T. Pitassi, and D. Liu. Inapproximability of treewidth, one-shot pebbling, and related layout problems. J. Artificial Intelligence Res., 49:569–600, 2014. \hrefhttps://doi.org/10.1613/jair.4030 \pathdoi:10.1613/jair.4030.
[56] K. Yamazaki. Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis. Algorithms (Basel), 11(11):Paper No. 173, 10, 2018. \hrefhttps://doi.org/10.3390/a11110173 \pathdoi:10.3390/a11110173.

Appendix A Selected Results from 3-Manifold Topology

In this appendix we collect important facts about the topology of 3-manifolds we rely on. We do not aim to reproduce their complete proofs; indeed, those are often quite technical or include lengthy case analyses. However, we do aim to give precise statements and references.

A.1 Weak reductions

Example A.1.

The $3$ -torus $\mathbb{T}^{3}=\mathbb{S}^{1}\times\mathbb{S}^{1}\times\mathbb{S}^{1}$ is a closed 3-manifold built by identifying opposite faces of a solid cube $K$ (\Creffig:3-torus). It is well-known that $\mathbb{T}^{3}$ has Heegaard genus $\mathfrak{g}\left(\mathbb{T}^{3}\right)=3$ . A genus-three Heegaard splitting $\mathscr{H}=(\mathcal{H}_{1},\mathcal{H}_{2},\mathcal{S})$ of $\mathbb{T}^{3}$ can be obtained as follows: Upon the face-identifications, the 1-skeleton of $K$ becomes a bouquet of three circles. We let $\mathcal{H}_{1}=\overline{N}_{\mathbb{T}^{3}}(\raisebox{-1.5pt}{\includegraphics[scale={.75}]{bouquet}})$ be a closed regular neighborhood of in $\mathbb{T}^{3}$ , $\mathcal{H}_{2}$ be the closure of $\mathbb{T}^{3}\setminus\mathcal{H}_{1}$ , and $\mathcal{S}=\mathcal{H}_{1}\cap\mathcal{H}_{2}$ be the resulting splitting surface (\Creffig:3-torus-splitting).

Note that $D_{1}$ and $D_{2}$ in \Creffig:3-torus-weak-reduction are essential disks in the handlebodies $\mathcal{H}_{1}$ and $\mathcal{H}_{2}$ , respectively, and $\partial D_{1}\cap\partial D_{2}=\emptyset$ , hence the splitting $\mathscr{H}=(\mathcal{H}_{1},\mathcal{H}_{2},\mathcal{S})$ is weakly reducible. Now, a weak reduction at $\mathcal{S}$ may be carried out as presented on \Creffig:schemata-weak-reduction. We refer to [49, p. 108–111] for details (cf. [48, p. 61–62]).

{subfigure}

[b]0.3 \begin{overpic}[scale={1.05}]{heegaard-splitting-schematic} \put(1.0,39.0){\small{$\mathcal{S}$}} \put(46.0,23.0){\small{$\mathcal{H}_{2}$}} \put(46.0,54.0){\small{$\mathcal{H}_{1}$}} \put(102.5,54.0){\LARGE{$\leadsto$}} \end{overpic} {subfigure}[b]0.3 \begin{overpic}[scale={1.05}]{weak-reducing-disks} \put(1.0,39.0){\small{$\mathcal{S}$}} \put(62.0,0.0){\small{$D_{2}$}} \put(60.0,46.0){\small{$\partial D_{2}$}} \put(29.5,76.5){\small{$D_{1}$}} \put(27.5,30.5){\small{$\partial D_{1}$}} \put(102.5,54.0){\LARGE{$\leadsto$}} \end{overpic} {subfigure}[b]0.3 \begin{overpic}[scale={1.05}]{weak-reduction-schematic} \end{overpic}

{subfigure}

[b]1 \begin{overpic}[scale={1.05}]{weak-reduction-schematic-colors} \put(46.75,19.0){\small{$\mathcal{S}$}} \put(42.0,12.0){\small{$\mathcal{H}_{2}$}} \put(51.0,12.0){\small{$\mathcal{H}_{1}$}} \put(74.75,19.0){\small{$\mathcal{S}_{2}$}} \put(70.0,12.0){\small{$\mathcal{C}^{(2)}_{1}$}} \put(79.0,12.0){\small{$\mathcal{C}^{(2)}_{2}$}} \put(92.5,19.0){\small{$\mathcal{S}_{1}$}} \put(87.75,12.0){\small{$\mathcal{C}^{(1)}_{1}$}} \put(96.75,12.0){\small{$\mathcal{C}^{(1)}_{2}$}} \put(37.5,4.0){\small{$0pt(\mathscr{H})=(g(\mathcal{S}))=(3)$}} \put(68.5,4.0){\small{$0pt(\mathscr{H}^{\prime})=(g(\mathcal{S}_{1}),g(\mathcal{S}_{2}))=(2,2)$}} \put(60.0,16.0){\Large{$\leadsto$}} \put(8.5,5.5){\small{$\mathcal{C}^{(2)}_{1}$}} \put(19.25,18.0){\small{$\mathcal{C}^{(1)}_{2}$}} \put(0.0,9.0){\small{$\mathcal{S}_{2}$}} \put(0.0,14.5){\small{$\mathcal{S}_{1}$}} \put(30.25,8.0){\small{$\mathcal{C}^{(2)}_{2}$}} \put(30.25,15.5){\small{$\mathcal{C}^{(1)}_{1}$}} \end{overpic}

Figure 22: Schematic “movie” of a weak reduction of the genus-three Heegaard splitting of

\mathbb{T}^{3}

A.2 Seifert fibered spaces and JSJ decompositions

A key assertion about the manifold $\mathscr{M}_{G}$ constructed in \Crefsec:const is \Crefclaim:jsj, according to which the dual graph $\Gamma(\mathscr{D})$ of the JSJ decomposition $\mathscr{D}$ of $\mathscr{M}_{G}$ satisfies $\Gamma(\mathscr{D})=G$ . This can be shown through the same argument that is outlined by Lackenby in [37, p. 591]. However, while we use the same building blocks as Lackenby (namely the manifolds $\mathscr{N}(k)$ ), we glue them together via different (high-distance) maps. Therefore, some explanations are in order. To this end, closely following [23], we recall some basic definitions and important results.

Seifert fiberings

A model Seifert fibering of the solid torus $\mathbb{S}^{1}\times D$ is a decomposition of $\mathbb{S}^{1}\times D$ into disjoint circles, called fibers, obtained as follows. Consider the solid cylinder $[0,1]\times D$ and identify its boundary disks $\{0\}\times D$ and $\{1\}\times D$ through a rotation by $2\pi p/q$ , where $p$ and $q$ are relatively prime integers with $q>0$ . After this identification the segment $[0,1]\times\{0\}$ becomes a fiber $\mathbb{S}^{1}\times\{0\}$ , whereas every other fiber consists of $q$ segments of the form $[0,1]\times\{x\}$ . Next, a Seifert fibering of $3$ -manifold $\mathscr{M}$ is a decomposition of $\mathscr{M}$ into disjoint circles (also called fibers), such that each fiber has a neighborhood homeomorphic to that of a fiber in some model Seifert fibering of $\mathbb{S}^{1}\times D$ via a fiber-preserving homeomorphism. A $3$ -manifold that admits a Seifert fibering is called a Seifert fibered space. The following classical result says that most Seifert fibered spaces admit a unique Seifert fibering.

Theorem A.2 ([44, 54], adapted from [23, Theorem 2.3]).

Every orientable Seifert fibered space admits a unique Seifert fibering up to fiber-preserving homeomorphism, except for:

•

$\mathbb{S}^{1}\times D$ , the solid torus (various model fiberings; see above),
•

$\mathbb{S}^{1}\mathbin{\stackrel{{\scriptstyle\sim}}{{\smash{\times}\rule{0.0pt}{3.87495pt}}}}\mathbb{S}^{1}\mathbin{\stackrel{{\scriptstyle\sim}}{{\smash{\times}\rule{0.0pt}{3.87495pt}}}}I$ , the orientable $\mathbb{S}^{1}$ -bundle over the Möbius band (two fiberings),
•

Seifert fibered spaces over $\mathbb{R}P^{2}$ with one exceptional fiber (two fiberings),
•

lens spaces $L(p,q)$ including $\mathbb{S}^{3}$ and $\mathbb{S}^{1}\times\mathbb{S}^{2}$ (various fiberings), and
•

$\mathbb{S}^{1}\mathbin{\stackrel{{\scriptstyle\sim}}{{\smash{\times}\rule{0.0pt}{3.87495pt}}}}\mathbb{S}^{1}\mathbin{\stackrel{{\scriptstyle\sim}}{{\smash{\times}\rule{0.0pt}{3.87495pt}}}}\mathbb{S}^{1}$ , the orientable $\mathbb{S}^{1}$ -bundle over the Klein bottle (two fiberings).

Corollary A.3.

The manifolds $\mathscr{N}(k)$ defined in \Crefsec:const admit unique Seifert fiberings.

Proof A.4.

The statement follows by observing that $\mathscr{N}(k)$ is a Seifert fibered space over the torus, and so it does not belong to any of the exceptional manifolds mentioned in \Crefthm:seifert-uniqueness.

Proposition A.5 (folklore, see [23, Proposition 1.6]).

If an irreducible $3$ -manifold $\widetilde{\mathscr{M}}$ is a covering space of the interior of another $3$ -manifold $\mathscr{M}$ , then $\mathscr{M}$ is irreducible as well.

Claim 3 (folklore, see [23, p. 11]).

For any compact, connected and orientable surface $F$ (possibly with boundary) other than $\mathbb{S}^{2}$ , the interior of $F\times\mathbb{S}^{1}$ has $\mathbb{R}^{3}$ as its universal cover.¹⁴¹⁴14The claim holds for non-orientable surfaces as well with the exception of $\mathbb{R}P^{2}$ .

{claimproof}

If $F\ncong\mathbb{S}^{2}$ , it is well-known that the universal cover of $F$ is $\mathbb{R}^{2}$ . Indeed, for $F\cong\mathbb{T}^{2}$ a covering map $\mathbb{R}^{2}\rightarrow F$ can be defined through the regular tiling of the Euclidean plane via squares, while for $F\cong\mathbb{S}_{g}$ with genus $g>1$ such a map can be obtained through the regular tiling of the hyperbolic plane via regular $4g$ -gons, with $4g$ such polygons meeting at each vertex [20]. If $F$ has non-empty boundary, then by the theory of covering spaces [3, Theorem 10.19] the interior of $F$ has some universal cover $\mathscr{X}$ , and by the uniformization theorem [22, Theorem XII.0.1], this space $\mathscr{X}$ – being a non-compact, open, simply-connected surface – must be homeomorphic to $\mathbb{R}^{2}$ . As the universal cover of $\mathbb{S}^{1}$ is $\mathbb{R}$ , it follows that the universal cover of $F\times\mathbb{S}^{1}$ is $\mathbb{R}^{3}$ .

Claim 4 (folklore, see [23, p. 14]).

A $2$ -sided torus $T\subset\mathscr{M}$ in an irreducible 3-manifold $\mathscr{M}$ is compressible if and only if $T$ either bounds a solid torus $\mathbb{S}^{1}\times D\subset\mathscr{M}$ or lies in a ball in $\mathscr{M}$ .

Corollary A.6.

For any $k\in\mathbb{N}$ , $\mathscr{N}(k)$ is irreducible and has incompressible boundary.

Proof A.7.

The irreducibility of $\mathscr{N}(k)$ is a consequence of \Crefprop:irreducible-cover and \Crefclaim:surface-cover. Then, the incompressibility of $\partial\mathscr{N}(k)$ follows from \Crefclaim:compressible-torus by noting that $\partial\mathscr{N}(k)$ is a union of tori and, by construction of $\mathscr{N}(k)$ , none of them bounds a solid torus or lies in a ball in $\mathscr{N}(k)$ .

Proposition A.8.

The manifold $\mathscr{M}_{G}$ constructed in \Crefsec:const is irreducible.

Proof A.9.

Let $G=(V,E)$ be a multigraph on $n$ nodes with $m$ arcs, and $\mathbf{T}=\{T_{1},\ldots,T_{m}\}$ be the collection of pairwise disjoint tori $T_{i}\subset\mathscr{M}_{G}$ that are the images of the boundary tori of the manifolds $\mathscr{N}_{v}\cong\mathscr{N}(d_{v})$ after performing the torus-gluings in the construction of $\mathscr{M}_{G}$ .

Let us assume that $\mathscr{M}_{G}$ is not irreducible, i.e., there is some reducing 2-sphere $S\subset\mathscr{M}_{G}$ . By definition, $S$ does not bound a ball in $\mathscr{M}_{G}$ . Note that $S$ cannot be entirely contained in any of the building blocks $\mathscr{N}_{v}\subset\mathscr{M}_{G}$ , otherwise it would imply the reducibility of $\mathscr{N}_{v}\cong\mathscr{N}(d_{v})$ , contradicting \Crefcor:irreducible. It follows that $S\cap(\cup_{i=1}^{m}T_{i})\neq\emptyset$ . Thus, after an isotopy if necessary, we may assume that $S$ intersects $\cup_{i=1}^{m}T_{i}$ transversally, and the intersection $S\cap(\cup_{i=1}^{m}T_{i})$ is a union of pairwise disjoint closed curves $\boldsymbol{\alpha}=\{\alpha_{1},\ldots,\alpha_{\ell}\}$ with $\ell$ being minimal.

Now let $\alpha_{j}\in\boldsymbol{\alpha}$ be a curve that is innermost in $S$ , i.e., one of the two disks bounded by $\alpha_{j}$ in $S$ , say $D\subset S$ , does not contain any other curves from $\boldsymbol{\alpha}$ . After relabeling if necessary, let $T_{j}\in\mathbf{T}$ denote the torus for which $\alpha_{j}=S\cap T_{j}$ . Note that, if $\alpha_{j}$ also bounds a disk $D^{\prime}\subset T_{j}$ , then $D\cup D^{\prime}$ is a sphere entirely contained in one of the building blocks $\mathscr{N}_{w}$ incident to $T_{j}$ . Since $\mathscr{N}_{w}$ is irreducible (\Crefcor:irreducible), $D\cup D^{\prime}$ bounds a ball $B\subset\mathscr{N}_{w}$ , which can be used to eliminate $\alpha_{j}$ by first isotoping $D$ inside $B$ to coincide with $D^{\prime}$ and then pushing $D^{\prime}$ off the torus $T_{j}$ , contradicting the minimality of $\boldsymbol{\alpha}$ . Hence the disk $D$ is essential in $\mathscr{N}_{w}$ . However, this contradicts the incompressibility of $T_{j}$ in $\mathscr{N}_{w}$ (\Crefcor:irreducible).

Proof A.10 (Proof of \Crefclaim:jsj).

We follow the notation introduced in the proof of \Crefprop:irreducible-MG. By \Crefcor:seifert-uniqueness-blocks, each building block $\mathscr{N}_{v}$ admits a unique Seifert fibering. In particular, each boundary component of $\mathscr{N}_{v}$ has a uniquely determined fibering. Therefore, when two building blocks $\mathscr{N}_{u}$ and $\mathscr{N}_{u^{\prime}}$ are glued together along boundary tori $T\subset\partial\mathscr{N}_{u}$ and $T^{\prime}\subset\partial\mathscr{N}_{u^{\prime}}$ , the resulting 3-manifold is not Seifert fibered, unless the gluing map aligns the (identical) Seifert fiberings of $T$ and $T^{\prime}$ . Now, it follows from the definition of distance [6, Section 4.1] that gluing maps of distance at least one do not align these Seifert fiberings. (In fact, for any two fixed Seifert fiberings of the torus, there are precisely two maps that align them.) Hence, upon the manifold $\mathscr{M}_{G}$ is constructed, the Seifert fibrations of adjacent building blocks induce different fibrations on each torus in $\mathbf{T}=\{T_{1},\ldots,T_{m}\}$ . Now, by construction of the building blocks, none of the tori in $\mathbf{T}$ bounds a solid torus (cf. [37, p. 591]), therefore they are all incompressible (cf. \Crefclaim:compressible-torus) and pairwise non-parallel. This implies that the building blocks $\mathscr{N}_{v}$ ( $v\in V$ ) are indeed the JSJ pieces of $\mathscr{M}_{G}$ and the tori in $\mathbf{T}$ comprise its JSJ tori.

Appendix B Triangulating the building blocks

Here we describe the triangulation $\mathscr{T}(k)$ of the building block $\mathscr{N}(k)$ introduced in \Crefsec:const. Topologically, $\mathscr{N}(k)=\mathbb{T}^{2}_{k}\times\mathbb{S}^{1}$ , where $\mathbb{T}^{2}_{k}$ is obtained by removing the interiors of $k$ pairwise disjoint disks from the torus $\mathbb{T}^{2}$ . To construct $\mathscr{T}(k)$ , first we triangulate $\mathbb{T}^{2}_{k}$ with $3k+2$ triangles as shown in \Creffig:torus+holes. This triangulation of $\mathbb{T}^{2}_{k}$ naturally lifts to a decomposition of $\mathbb{T}^{2}_{k}\times[0,1]$ into $3k+2$ triangular prisms, each of which can be triangulated with three tetrahedra, see \Creffig:trg_prism. The construction of $\mathscr{T}(k)$ is concluded by identifying the triangulations of $\mathbb{T}^{2}_{k}\times\{0\}$ and $\mathbb{T}^{2}_{k}\times\{1\}$ via the identity map. It immediately follows that $\mathscr{T}(k)$ consists of $9k+6=O(k)$ tetrahedra and induces a two-triangle triangulation at each boundary torus.

Acknowledgements.

On the Width of Complicated JSJ Decompositions

Abstract

keywords:

1 Introduction

The main result

Theorem 1.1 (Width inheritance).

An algorithmic construction

Theorem 1.2.

Applications

Proof 1.3 (Outline of the proof of Theorem 1.1).

Organization of the paper

2 Preliminaries

2.1 Graphs

2.2 Manifolds

3-Manifolds and surfaces

Triangulations and the treewidth of 3-manifolds

Incompressible surfaces and essential disks

Heegaard splittings of closed 3-manifolds

The JSJ decomposition

3 Generalized Heegaard Splittings

3.1 Compression bodies and forks

Non-faithful forks

Spines and sweep-outs of compression bodies

Remark 3.1 (Sweep-out along a fork).

3.2 Generalized Heegaard splittings and fork complexes

Heegaard splittings revisited

Proposition 3.2 ([49, Theorem 2.1.11], cf. [26, Appendix B]).

Generalized Heegaard splittings

Sweep-outs of 3-manifolds

The width of a generalized Heegaard splitting

3.3 Weak reductions

Theorem 3.3 ([49, Lemma 5.2.4], [50, Rule 5]).

4 The Main Result

Definition 4.1.

Proof 4.2 (Proof of inequality (1)).

Proof 4.3 (Proof of inequality (2)).

5 An Algorithmic Construction

The building blocks

Overview of the construction of 𝓜𝑮\boldsymbol{\mathscr{M}_{G}}

Claim 1 (name=Based on [37, p. 591], label=claim:jsj).

High-distance torus gluings

Theorem 5.1 ([6, Appendix], [4, Theorem 5.4]131313The notation and the statement of \Crefthm:distance have been adapted to match the present context.).

Triangulating the gluing maps

Lemma 5.2 ([6, Lemma 4.6]).

Claim 2.

Lemma 5.3 (Folklore, cf. [9, Lemma A. 1]).

Proof 5.4 (Finishing the proof of \Crefthm:construction).

6 Applications

Corollary 6.1.

Corollary 6.2.

Proof 6.3 (Proof of \Crefcor:unbounded-pathwidth,cor:unbounded-treewidth).

Corollary 6.4.

Proof 6.5.

Remark 6.6.

7 Discussion and Open Problems

Question 7.1.

Question 7.2.

References

Appendix A Selected Results from 3-Manifold Topology

A.1 Weak reductions

Example A.1.

A.2 Seifert fibered spaces and JSJ decompositions

Seifert fiberings

Theorem A.2 ([44, 54], adapted from [23, Theorem 2.3]).

Corollary A.3.

Proof A.4.

Proposition A.5 (folklore, see [23, Proposition 1.6]).

Claim 3 (folklore, see [23, p. 11]).

Claim 4 (folklore, see [23, p. 14]).

Corollary A.6.

Proof A.7.

Proposition A.8.

Proof A.9.

Proof A.10 (Proof of \Crefclaim:jsj).

Appendix B Triangulating the building blocks

Overview of the construction of $\boldsymbol{\mathscr{M}_{G}}$

Theorem 5.1 ([6, Appendix], [4, Theorem 5.4]¹³¹³13The notation and the statement of \Crefthm:distance have been adapted to match the present context.).