<p>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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathscr {M}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">M</mi> </math></EquationSource> </InlineEquation> yields a linear lower bound on its treewidth <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\operatorname {tw} (\mathscr {M})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>tw</mo> <mo stretchy="false">(</mo> <mi mathvariant="script">M</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> (resp. pathwidth <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\operatorname {pw} (\mathscr {M})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>pw</mo> <mo stretchy="false">(</mo> <mi mathvariant="script">M</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>), defined as the smallest treewidth (resp. pathwidth) of the dual graph of any triangulation of <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\mathscr {M}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">M</mi> </math></EquationSource> </InlineEquation>. 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.</p>

On the Width of Complicated JSJ Decompositions

期刊论文
出版模式：

开放获取
发表日期：

2025年6月28日

查看全文

Kristóf Huszár,
Jonathan Spreer

摘要

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