{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T20:29:51Z","timestamp":1764361791968,"version":"3.46.0"},"reference-count":57,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,6,28]],"date-time":"2025-06-28T00:00:00Z","timestamp":1751068800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,6,28]],"date-time":"2025-06-28T00:00:00Z","timestamp":1751068800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-19-P3IA-0002","ANR-20-CE48-0007","ANR-18-CE40-0032","ANR-21-CE48-0014"],"award-info":[{"award-number":["ANR-19-P3IA-0002","ANR-20-CE48-0007","ANR-18-CE40-0032","ANR-21-CE48-0014"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-10-LABX-59-01"],"award-info":[{"award-number":["ANR-10-LABX-59-01"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["DP220102588"],"award-info":[{"award-number":["DP220102588"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    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 \u201csufficiently complicated\u201d JSJ decomposition of a 3-manifold enforces a \u201ccomplicated structure\u201d 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\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\mathscr {M}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>M<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    yields a linear lower bound on its treewidth\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\operatorname {tw} (\\mathscr {M})$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mo>tw<\/mml:mo>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>M<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    (resp. pathwidth\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\operatorname {pw} (\\mathscr {M})$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mo>pw<\/mml:mo>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>M<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    ), defined as the smallest treewidth (resp. pathwidth) of the dual graph of any triangulation of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\mathscr {M}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>M<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . 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\u2014previously 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.\n                  <\/jats:p>","DOI":"10.1007\/s00454-025-00746-1","type":"journal-article","created":{"date-parts":[[2025,6,28]],"date-time":"2025-06-28T13:52:03Z","timestamp":1751118723000},"page":"917-943","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Width of Complicated JSJ Decompositions"],"prefix":"10.1007","volume":"74","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5445-5057","authenticated-orcid":false,"given":"Krist\u00f3f","family":"Husz\u00e1r","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6865-9483","authenticated-orcid":false,"given":"Jonathan","family":"Spreer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,6,28]]},"reference":[{"key":"746_CR1","doi-asserted-by":"publisher","unstructured":"Moise, E.E.: Affine structures in $$3$$-manifolds. V. The triangulation theorem and Hauptvermutung. Ann. Math. (2) 56, 96\u2013114 (1952) https:\/\/doi.org\/10.2307\/1969769","DOI":"10.2307\/1969769"},{"issue":"1","key":"746_CR2","doi-asserted-by":"publisher","first-page":"189","DOI":"10.2140\/pjm.2019.301.189","volume":"301","author":"G Kuperberg","year":"2019","unstructured":"Kuperberg, G.: Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization. Pacific J. Math. 301(1), 189\u2013241 (2019). https:\/\/doi.org\/10.2140\/pjm.2019.301.189","journal-title":"Pacific J. Math."},{"key":"746_CR3","doi-asserted-by":"publisher","unstructured":"Lackenby, M.: Algorithms in 3-manifold theory. In: Agol, I., Gabai, D. (eds.) Surveys in $$3$$-manifold Topology and Geometry. Surv. Differ. Geom., vol. 25, pp. 163\u2013213. Int. Press, Boston (2020). https:\/\/doi.org\/10.4310\/SDG.2020.v25.n1.a5","DOI":"10.4310\/SDG.2020.v25.n1.a5"},{"issue":"4","key":"746_CR4","doi-asserted-by":"publisher","first-page":"2431","DOI":"10.2140\/agt.2014.14.2431","volume":"14","author":"P Scott","year":"2014","unstructured":"Scott, P., Short, H.: The homeomorphism problem for closed 3-manifolds. Algebr. Geom. Topol. 14(4), 2431\u20132444 (2014). https:\/\/doi.org\/10.2140\/agt.2014.14.2431","journal-title":"Algebr. Geom. Topol."},{"key":"746_CR5","unstructured":"Manolescu, C.: Lectures on the triangulation conjecture. In: Proc. 22nd G\u00f6kova Geom.-Topol. Conf. (GGT 2015), pp. 1\u201338. Int. Press, Boston (2016). https:\/\/gokovagt.org\/proceedings\/2015\/manolescu.html"},{"key":"746_CR6","first-page":"218","volume":"121","author":"A Markov","year":"1958","unstructured":"Markov, A.: The insolubility of the problem of homeomorphy (in Russian). Dokl. Akad. Nauk SSSR 121, 218\u2013220 (1958)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"746_CR7","doi-asserted-by":"publisher","unstructured":"Poonen, B.: Undecidable problems: a sampler. In: Interpreting G\u00f6del, pp. 211\u2013241. Cambridge Univ. Press, Cambridge (2014). https:\/\/doi.org\/10.1017\/CBO9780511756306.015","DOI":"10.1017\/CBO9780511756306.015"},{"key":"746_CR8","doi-asserted-by":"publisher","unstructured":"Burton, B.A., Downey, R.G.: Courcelle\u2019s theorem for triangulations. J. Comb. Theory, Ser. A 146, 264\u2013294 (2017) https:\/\/doi.org\/10.1016\/j.jcta.2016.10.001","DOI":"10.1016\/j.jcta.2016.10.001"},{"issue":"1","key":"746_CR9","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1145\/2738034","volume":"42","author":"BA Burton","year":"2016","unstructured":"Burton, B.A., Lewiner, T., Paix\u00e3o, J., Spreer, J.: Parameterized complexity of discrete Morse theory. ACM Trans. Math. Softw. 42(1), 6\u20131624 (2016). https:\/\/doi.org\/10.1145\/2738034","journal-title":"ACM Trans. Math. Softw."},{"issue":"1\u20132","key":"746_CR10","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s41468-018-0016-2","volume":"2","author":"BA Burton","year":"2018","unstructured":"Burton, B.A., Maria, C., Spreer, J.: Algorithms and complexity for Turaev-Viro invariants. J. Appl. Comput. Topol. 2(1\u20132), 33\u201353 (2018). https:\/\/doi.org\/10.1007\/s41468-018-0016-2","journal-title":"J. Appl. Comput. Topol."},{"key":"746_CR11","doi-asserted-by":"publisher","unstructured":"Burton, B.A., Pettersson, W.: Fixed parameter tractable algorithms in combinatorial topology. In: Proc. 20th Int. Conf. Comput. Comb. (COCOON 2014), pp. 300\u2013311 (2014). https:\/\/doi.org\/10.1007\/978-3-319-08783-2_26","DOI":"10.1007\/978-3-319-08783-2_26"},{"key":"746_CR12","doi-asserted-by":"publisher","unstructured":"Burton, B.A., Spreer, J.: The complexity of detecting taut angle structures on triangulations. In: Proc. 24th Annu. ACM-SIAM Symp. Discrete Algorithms (SODA 2013), pp. 168\u2013183 (2013). https:\/\/doi.org\/10.1137\/1.9781611973105.13","DOI":"10.1137\/1.9781611973105.13"},{"key":"746_CR13","doi-asserted-by":"publisher","unstructured":"Bagchi, B., Burton, B.A., Datta, B., Singh, N., Spreer, J.: Efficient algorithms to decide tightness. In: 32nd Int. Symp. Comput. Geom. (SoCG 2016). LIPIcs. Leibniz Int. Proc. Inf., vol. 51, pp. 12\u201311215. Schloss Dagstuhl\u2013Leibniz-Zent. Inf., Dagstuhl, Germany (2016). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2016.12","DOI":"10.4230\/LIPIcs.SoCG.2016.12"},{"key":"746_CR14","doi-asserted-by":"publisher","unstructured":"Burton, B.A.: Computational topology with Regina: algorithms, heuristics and implementations. In: Geometry and Topology Down Under. Contemp. Math., vol. 597, pp. 195\u2013224. Am. Math. Soc., Providence, RI (2013). https:\/\/doi.org\/10.1090\/conm\/597\/11877","DOI":"10.1090\/conm\/597\/11877"},{"key":"746_CR15","unstructured":"Burton, B.A., Budney, R., Pettersson, W., et al.: Regina: Software for low-dimensional topology (1999\u20132023). https:\/\/regina-normal.github.io"},{"key":"746_CR16","doi-asserted-by":"publisher","unstructured":"Husz\u00e1r, K.: Combinatorial width parameters for $$3$$-dimensonal manifolds. PhD thesis, IST Austria (June 2020). https:\/\/doi.org\/10.15479\/AT:ISTA:8032","DOI":"10.15479\/AT:ISTA:8032"},{"issue":"1","key":"746_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.57717\/cgt.v1i1.4","volume":"1","author":"K Husz\u00e1r","year":"2022","unstructured":"Husz\u00e1r, K.: On the pathwidth of hyperbolic 3-manifolds. Comput. Geom. Topol. 1(1), 1\u201319 (2022). https:\/\/doi.org\/10.57717\/cgt.v1i1.4","journal-title":"Comput. Geom. Topol."},{"key":"746_CR18","doi-asserted-by":"publisher","unstructured":"Husz\u00e1r, K., Spreer, J.: 3-Manifold triangulations with small treewidth. In: 35th Int. Symp. Comput. Geom. (SoCG 2019). LIPIcs. Leibniz Int. Proc. Inf., vol. 129, pp. 44\u201314420. Schloss Dagstuhl\u2013Leibniz-Zent. Inf., Dagstuhl, Germany (2019). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2019.44","DOI":"10.4230\/LIPIcs.SoCG.2019.44"},{"issue":"2","key":"746_CR19","doi-asserted-by":"publisher","first-page":"70","DOI":"10.20382\/jogc.v10i2a5","volume":"10","author":"K Husz\u00e1r","year":"2019","unstructured":"Husz\u00e1r, K., Spreer, J., Wagner, U.: On the treewidth of triangulated 3-manifolds. J. Comput. Geom. 10(2), 70\u201398 (2019). https:\/\/doi.org\/10.20382\/jogc.v10i2a5","journal-title":"J. Comput. Geom."},{"issue":"5","key":"746_CR20","doi-asserted-by":"publisher","first-page":"2625","DOI":"10.2140\/agt.2019.19.2625","volume":"19","author":"C Maria","year":"2019","unstructured":"Maria, C., Purcell, J.: Treewidth, crushing and hyperbolic volume. Algebr. Geom. Topol. 19(5), 2625\u20132652 (2019). https:\/\/doi.org\/10.2140\/agt.2019.19.2625","journal-title":"Algebr. Geom. Topol."},{"key":"746_CR21","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1023\/B:GEOM.0000006584.85248.c5","volume":"102","author":"I Agol","year":"2003","unstructured":"Agol, I.: Small 3-manifolds of large genus. Geom. Dedicata 102, 53\u201364 (2003). https:\/\/doi.org\/10.1023\/B:GEOM.0000006584.85248.c5","journal-title":"Geom. Dedicata"},{"key":"746_CR22","doi-asserted-by":"publisher","unstructured":"Jaco, W., Shalen, P.B.: A new decomposition theorem for irreducible sufficiently-large $$3$$-manifolds. In: Algebraic and Geometric Topology. Proc. Sympos. Pure Math., vol. 32, part 2, pp. 71\u201384. Am. Math. Soc., Providence, RI (1978). https:\/\/doi.org\/10.1090\/pspum\/032.2\/520524","DOI":"10.1090\/pspum\/032.2\/520524"},{"issue":"220","key":"746_CR23","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1090\/memo\/0220","volume":"21","author":"WH Jaco","year":"1979","unstructured":"Jaco, W.H., Shalen, P.B.: Seifert fibered spaces in $$3$$-manifolds. Mem. Am. Math. Soc. 21(220), 192 (1979). https:\/\/doi.org\/10.1090\/memo\/0220","journal-title":"Mem. Am. Math. Soc."},{"key":"746_CR24","doi-asserted-by":"publisher","unstructured":"Johannson, K.: Homotopy Equivalences of $$3$$-manifolds with Boundaries. Lect. Notes Math., vol. 761, p. 303. Springer, Berlin (1979). https:\/\/doi.org\/10.1007\/BFb0085406","DOI":"10.1007\/BFb0085406"},{"key":"746_CR25","doi-asserted-by":"publisher","unstructured":"Scharlemann, M., Schultens, J., Saito, T.: Lecture Notes on Generalized Heegaard Splittings, p. 130. World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ (2016). https:\/\/doi.org\/10.1142\/10019","DOI":"10.1142\/10019"},{"issue":"3\u20134","key":"746_CR26","doi-asserted-by":"publisher","first-page":"1137","DOI":"10.1007\/s00208-015-1314-9","volume":"365","author":"D Bachman","year":"2016","unstructured":"Bachman, D., Derby-Talbot, R., Sedgwick, E.: Heegaard structure respects complicated JSJ decompositions. Math. Ann. 365(3\u20134), 1137\u20131154 (2016). https:\/\/doi.org\/10.1007\/s00208-015-1314-9","journal-title":"Math. Ann."},{"key":"746_CR27","doi-asserted-by":"publisher","unstructured":"Bachman, D., Derby-Talbot, R., Sedgwick, E.: Computing Heegaard genus is NP-hard. In: A Journey Through Discrete Mathematics: A Tribute to Ji\u0159\u00ed Matou\u0161ek, pp. 59\u201387. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-44479-6_3","DOI":"10.1007\/978-3-319-44479-6_3"},{"issue":"2","key":"746_CR28","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1007\/s00208-012-0802-4","volume":"355","author":"D Bachman","year":"2013","unstructured":"Bachman, D.: Stabilizing and destabilizing Heegaard splittings of sufficiently complicated 3-manifolds. Math. Ann. 355(2), 697\u2013728 (2013). https:\/\/doi.org\/10.1007\/s00208-012-0802-4","journal-title":"Math. Ann."},{"key":"746_CR29","doi-asserted-by":"publisher","first-page":"171","DOI":"10.2140\/agt.2006.6.171","volume":"6","author":"D Bachman","year":"2006","unstructured":"Bachman, D., Schleimer, S., Sedgwick, E.: Sweepouts of amalgamated 3-manifolds. Algebr. Geom. Topol. 6, 171\u2013194 (2006). https:\/\/doi.org\/10.2140\/agt.2006.6.171","journal-title":"Algebr. Geom. Topol."},{"key":"746_CR30","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/s10711-004-6553-y","volume":"109","author":"M Lackenby","year":"2004","unstructured":"Lackenby, M.: The Heegaard genus of amalgamated 3-manifolds. Geom. Dedicata 109, 139\u2013145 (2004). https:\/\/doi.org\/10.1007\/s10711-004-6553-y","journal-title":"Geom. Dedicata"},{"issue":"4","key":"746_CR31","doi-asserted-by":"publisher","first-page":"1871","DOI":"10.2140\/gt.2010.14.1871","volume":"14","author":"T Li","year":"2010","unstructured":"Li, T.: Heegaard surfaces and the distance of amalgamation. Geom. Topol. 14(4), 1871\u20131919 (2010). https:\/\/doi.org\/10.2140\/gt.2010.14.1871","journal-title":"Geom. Topol."},{"issue":"2","key":"746_CR32","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1090\/S0002-9947-00-02654-4","volume":"353","author":"M Scharlemann","year":"2001","unstructured":"Scharlemann, M., Schultens, J.: Comparing Heegaard and JSJ structures of orientable 3-manifolds. Trans. Am. Math. Soc. 353(2), 557\u2013584 (2001). https:\/\/doi.org\/10.1090\/S0002-9947-00-02654-4","journal-title":"Trans. Am. Math. Soc."},{"key":"746_CR33","doi-asserted-by":"publisher","unstructured":"Schultens, J., Weidmann, R.: Destabilizing amalgamated Heegaard splittings. In: Workshop on Heegaard Splittings. Geom. Topol. Monogr., vol. 12, pp. 319\u2013334. Geom. Topol. Publ., Coventry (2007). https:\/\/doi.org\/10.2140\/gtm.2007.12.319","DOI":"10.2140\/gtm.2007.12.319"},{"key":"746_CR34","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D.: Graph expansion and the unique games conjecture. In: Proc. 2010 ACM Int. Symp. Theor. Comput. (STOC\u201910), pp. 755\u2013764. ACM, New York (2010)","DOI":"10.1145\/1806689.1806792"},{"key":"746_CR35","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1613\/jair.4030","volume":"49","author":"Y Wu","year":"2014","unstructured":"Wu, Y., Austrin, P., Pitassi, T., Liu, D.: Inapproximability of treewidth, one-shot pebbling, and related layout problems. J. Artificial Intelligence Res. 49, 569\u2013600 (2014). https:\/\/doi.org\/10.1613\/jair.4030","journal-title":"J. Artificial Intelligence Res."},{"issue":"11","key":"746_CR36","doi-asserted-by":"publisher","first-page":"173","DOI":"10.3390\/a11110173","volume":"11","author":"K Yamazaki","year":"2018","unstructured":"Yamazaki, K.: Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis. Algorithms (Basel) 11(11), 173\u201310 (2018). https:\/\/doi.org\/10.3390\/a11110173","journal-title":"Algorithms (Basel)"},{"key":"746_CR37","doi-asserted-by":"publisher","unstructured":"Schultens, J.: Introduction to $$3$$-Manifolds. Grad. Stud. Math., vol. 151, p. 286. Am. Math. Soc., Providence, RI (2014). https:\/\/doi.org\/10.1090\/gsm\/151","DOI":"10.1090\/gsm\/151"},{"issue":"69","key":"746_CR38","doi-asserted-by":"publisher","first-page":"37","DOI":"10.2307\/1970092","volume":"2","author":"RH Bing","year":"1959","unstructured":"Bing, R.H.: An alternative proof that $$3$$-manifolds can be triangulated. Ann. Math. 2(69), 37\u201365 (1959). https:\/\/doi.org\/10.2307\/1970092","journal-title":"Ann. Math."},{"key":"746_CR39","doi-asserted-by":"publisher","first-page":"161","DOI":"10.24033\/bsmf.968","volume":"44","author":"P Heegaard","year":"1916","unstructured":"Heegaard, P.: Sur l\u2019\"Analysis situs\". Bull. Soc. Math. France 44, 161\u2013242 (1916). https:\/\/doi.org\/10.24033\/bsmf.968","journal-title":"Bull. Soc. Math. France"},{"key":"746_CR40","unstructured":"Hatcher, A.: Notes on Basic 3-Manifold Topology. Available at https:\/\/pi.math.cornell.edu\/~hatcher\/3M\/3Mfds.pdf (accessed: February 14, 2024)"},{"key":"746_CR41","doi-asserted-by":"publisher","unstructured":"Scharlemann, M., Thompson, A.: Thin position for $$3$$-manifolds. In: Geometric Topology (Haifa, 1992). Contemp. Math., vol. 164, pp. 231\u2013238. Am. Math. Soc., Providence, RI (1994). https:\/\/doi.org\/10.1090\/conm\/164\/01596","DOI":"10.1090\/conm\/164\/01596"},{"key":"746_CR42","unstructured":"Scharlemann, M., Schultens, J., Saito, T.: Lecture notes on generalized Heegaard splittings. https:\/\/arxiv.org\/abs\/math\/0504167. Open-access version of [25] with slightly different structure. (2005)"},{"issue":"3","key":"746_CR43","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/0166-8641(87)90092-7","volume":"27","author":"AJ Casson","year":"1987","unstructured":"Casson, A.J., Gordon, C.M.: Reducing Heegaard splittings. Topology Appl. 27(3), 275\u2013283 (1987). https:\/\/doi.org\/10.1016\/0166-8641(87)90092-7","journal-title":"Topology Appl."},{"issue":"2","key":"746_CR44","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/s00222-005-0480-x","volume":"164","author":"M Lackenby","year":"2006","unstructured":"Lackenby, M.: Heegaard splittings, the virtually Haken conjecture and property $$(\\tau )$$. Invent. Math. 164(2), 317\u2013359 (2006). https:\/\/doi.org\/10.1007\/s00222-005-0480-x","journal-title":"Invent. Math."},{"issue":"3","key":"746_CR45","doi-asserted-by":"publisher","first-page":"580","DOI":"10.1007\/s00454-017-9905-8","volume":"58","author":"M Lackenby","year":"2017","unstructured":"Lackenby, M.: Some conditionally hard problems on links and 3-manifolds. Discrete Comput. Geom. 58(3), 580\u2013595 (2017). https:\/\/doi.org\/10.1007\/s00454-017-9905-8","journal-title":"Discrete Comput. Geom."},{"key":"746_CR46","unstructured":"Jaco, W., Rubinstein, J.H.: Layered-triangulations of 3-manifolds. https:\/\/arxiv.org\/abs\/math\/0603601. 97 pages, 32 figures (2006)"},{"issue":"4","key":"746_CR47","doi-asserted-by":"publisher","first-page":"871","DOI":"10.1007\/s00453-021-00875-y","volume":"84","author":"R Belmonte","year":"2022","unstructured":"Belmonte, R., Hanaka, T., Kanzaki, M., Kiyomi, M., Kobayashi, Y., Kobayashi, Y., Lampis, M., Ono, H., Otachi, Y.: Parameterized complexity of $$(A,\\ell )$$-path packing. Algorithmica 84(4), 871\u2013895 (2022). https:\/\/doi.org\/10.1007\/s00453-021-00875-y","journal-title":"Algorithmica"},{"issue":"1\u20132","key":"746_CR48","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209(1\u20132), 1\u201345 (1998). https:\/\/doi.org\/10.1016\/S0304-3975(97)00228-4","journal-title":"Theor. Comput. Sci."},{"issue":"9","key":"746_CR49","doi-asserted-by":"publisher","first-page":"3821","DOI":"10.1090\/S0002-9947-05-03919-X","volume":"358","author":"I Agol","year":"2006","unstructured":"Agol, I., Hass, J., Thurston, W.: The computational complexity of knot genus and spanning area. Trans. Am. Math. Soc. 358(9), 3821\u20133850 (2006). https:\/\/doi.org\/10.1090\/S0002-9947-05-03919-X","journal-title":"Trans. Am. Math. Soc."},{"key":"746_CR50","doi-asserted-by":"publisher","first-page":"107648","DOI":"10.1016\/j.aim.2021.107648","volume":"381","author":"A Mesmay","year":"2021","unstructured":"Mesmay, A., Rieck, Y., Sedgwick, E., Tancer, M.: The unbearable hardness of unknotting. Adv. Math. 381, 107648\u201336 (2021). https:\/\/doi.org\/10.1016\/j.aim.2021.107648","journal-title":"Adv. Math."},{"key":"746_CR51","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1090\/btran\/71","volume":"8","author":"D Koenig","year":"2021","unstructured":"Koenig, D., Tsvietkova, A.: NP-hard problems naturally arising in knot theory. Trans. Am. Math. Soc. Ser. B 8, 420\u2013441 (2021). https:\/\/doi.org\/10.1090\/btran\/71","journal-title":"Trans. Am. Math. Soc. Ser. B"},{"key":"746_CR52","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0040-9383(67)90013-4","volume":"6","author":"P Orlik","year":"1967","unstructured":"Orlik, P., Vogt, E., Zieschang, H.: Zur Topologie gefaserter dreidimensionaler Mannigfaltigkeiten. Topology 6, 49\u201364 (1967). https:\/\/doi.org\/10.1016\/0040-9383(67)90013-4","journal-title":"Zur Topologie gefaserter dreidimensionaler Mannigfaltigkeiten. Topology"},{"key":"746_CR53","doi-asserted-by":"crossref","unstructured":"Waldhausen, F.: Eine Klasse von $$3$$-dimensionalen Mannigfaltigkeiten. I, II. Invent. Math. 3, 308\u2013333487117 (1967). URL: https:\/\/eudml.org\/doc\/141878 and https:\/\/eudml.org\/doc\/141884 (accessed: February 14, 2024)","DOI":"10.1007\/BF01402956"},{"key":"#cr-split#-746_CR54.1","doi-asserted-by":"crossref","unstructured":"Coxeter, H.S.M.: Regular honeycombs in hyperbolic space. In: Proc. Int. Congr. Math., 1954, vol. 3, pp. 155-169. Erven P. Noordhoff","DOI":"10.1112\/plms\/s3-4.1.471"},{"key":"#cr-split#-746_CR54.2","unstructured":"North-Holland, Groningen-Amsterdam (1956). Available at https:\/\/www.mathunion.org\/fileadmin\/ICM\/Proceedings\/ICM1954.3\/ICM1954.3.ocr.pdf (accessed: February 14, 2024)"},{"key":"746_CR55","doi-asserted-by":"publisher","unstructured":"Armstrong, M.A.: Basic Topology. Undergrad. Texts Math., p. 251. Springer, New York-Berlin (1983). https:\/\/doi.org\/10.1007\/978-1-4757-1793-8","DOI":"10.1007\/978-1-4757-1793-8"},{"key":"746_CR56","doi-asserted-by":"publisher","unstructured":"Saint-Gervais, H.P.: 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\u00fcrich (2016). https:\/\/doi.org\/10.4171\/145","DOI":"10.4171\/145"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-025-00746-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-025-00746-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-025-00746-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T20:26:16Z","timestamp":1764361576000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-025-00746-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,28]]},"references-count":57,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["746"],"URL":"https:\/\/doi.org\/10.1007\/s00454-025-00746-1","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2025,6,28]]},"assertion":[{"value":"15 February 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 January 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 May 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 June 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflict of interest to declare.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"Not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Materials availability"}},{"value":"Not applicable.","order":6,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}}]}}