{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:32Z","timestamp":1740109592746,"version":"3.37.3"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,7,18]],"date-time":"2022-07-18T00:00:00Z","timestamp":1658102400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,7,18]],"date-time":"2022-07-18T00:00:00Z","timestamp":1658102400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1614562","1907612"],"award-info":[{"award-number":["1614562","1907612"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000153","name":"Division of Biological Infrastructure","doi-asserted-by":"publisher","award":["1759807"],"award-info":[{"award-number":["1759807"]}],"id":[{"id":"10.13039\/100000153","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006537","name":"Campus France","doi-asserted-by":"publisher","award":["ANR-16-CE40-0009-01","ANR-19-CE40-0014"],"award-info":[{"award-number":["ANR-16-CE40-0009-01","ANR-19-CE40-0014"]}],"id":[{"id":"10.13039\/501100006537","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006537","name":"Campus France","doi-asserted-by":"publisher","award":["ANR-11-LABX-0025-01","ANR-17-CE40-0033"],"award-info":[{"award-number":["ANR-11-LABX-0025-01","ANR-17-CE40-0033"]}],"id":[{"id":"10.13039\/501100006537","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1614562"],"award-info":[{"award-number":["1614562"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006537","name":"Campus France","doi-asserted-by":"publisher","award":["ANR-16-CE40-0009-01"],"award-info":[{"award-number":["ANR-16-CE40-0009-01"]}],"id":[{"id":"10.13039\/501100006537","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":[[2023,9]]},"DOI":"10.1007\/s00454-022-00411-x","type":"journal-article","created":{"date-parts":[[2022,7,18]],"date-time":"2022-07-18T16:20:37Z","timestamp":1658161237000},"page":"323-354","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Algorithms for Contractibility of Compressed Curves on 3-Manifold Boundaries"],"prefix":"10.1007","volume":"70","author":[{"given":"Erin Wolf","family":"Chambers","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francis","family":"Lazarus","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arnaud","family":"de Mesmay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Salman","family":"Parsa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,7,18]]},"reference":[{"issue":"9","key":"411_CR1","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)","journal-title":"Trans. Am. Math. Soc."},{"key":"411_CR2","doi-asserted-by":"crossref","unstructured":"Aschenbrenner, M., Friedl, S., Wilton, H.: Decision problems for $$3$$-manifolds and their fundamental groups. In: Interactions Between Low-Dimensional Topology and Mapping Class Groups (Bonn 2013). Geometry & Topology Monographs, vol. 19, pp. 201\u2013236. Geom. Topol. Publ., Coventry (2015)","DOI":"10.2140\/gtm.2015.19.201"},{"key":"411_CR3","doi-asserted-by":"crossref","unstructured":"Aschenbrenner, M., Friedl, S., Wilton, H.: $$3$$-Manifold Groups. EMS Series of Lectures in Mathematics. European Mathematical Society, Z\u00fcrich (2015)","DOI":"10.4171\/154"},{"key":"411_CR4","doi-asserted-by":"crossref","unstructured":"Bachman, D., Derby-Talbot, R., Sedgwick, E.: Computing Heegaard genus is NP-hard. In: A Journey Through Discrete Mathematics, pp. 59\u201387. Springer, Cham (2017)","DOI":"10.1007\/978-3-319-44479-6_3"},{"issue":"1","key":"411_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00454-021-00309-0","volume":"66","author":"MC Bell","year":"2021","unstructured":"Bell, M.C.: Simplifying triangulations. Discrete Comput. Geom. 66(1), 1\u201311 (2021)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"411_CR6","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/s00454-014-9572-y","volume":"52","author":"BA Burton","year":"2014","unstructured":"Burton, B.A.: A new approach to crushing $$3$$-manifold triangulations. Discrete Comput. Geom. 52(1), 116\u2013139 (2014)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"411_CR7","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.2140\/gt.2016.20.1061","volume":"20","author":"BA Burton","year":"2016","unstructured":"Burton, B.A., Colin de Verdi\u00e8re, \u00c9., de Mesmay, A.: On the complexity of immersed normal surfaces. Geom. Topol. 20(2), 1061\u20131083 (2016)","journal-title":"Geom. Topol."},{"key":"411_CR8","doi-asserted-by":"crossref","unstructured":"Colin de Verdi\u00e8re, \u00c9., Parsa, S.: Deciding contractibility of a non-simple curve on the boundary of a $$3$$-manifold. In: 28th Annual ACM-SIAM Symposium on Discrete Algorithms (Barcelona 2017), pp. 2691\u20132704. SIAM, Philadelphia (2017)","DOI":"10.1137\/1.9781611974782.178"},{"key":"411_CR9","unstructured":"Colin de Verdi\u00e8re, \u00c9., Parsa, S.: Deciding contractibility of a non-simple curve on the boundary of a $$3$$-manifold: a computational Loop Theorem (2020). arXiv:2001.04747"},{"issue":"3","key":"411_CR10","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/BF01456725","volume":"72","author":"M Dehn","year":"1912","unstructured":"Dehn, M.: Transformation der Kurven auf zweiseitigen Fl\u00e4chen. Math. Ann. 72(3), 413\u2013421 (1912)","journal-title":"Math. Ann."},{"issue":"6","key":"411_CR11","doi-asserted-by":"publisher","first-page":"#45","DOI":"10.1145\/3363367","volume":"66","author":"V Despr\u00e9","year":"2019","unstructured":"Despr\u00e9, V., Lazarus, F.: Computing the geometric intersection number of curves. J. ACM 66(6), #45 (2019)","journal-title":"J. ACM"},{"key":"411_CR12","doi-asserted-by":"crossref","unstructured":"Dynnikov, I.: Counting intersections of normal curves. J. Algebra 607(B), 181\u2013231 (2021)","DOI":"10.1016\/j.jalgebra.2021.09.010"},{"issue":"4","key":"411_CR13","doi-asserted-by":"publisher","first-page":"801","DOI":"10.4171\/JEMS\/98","volume":"9","author":"I Dynnikov","year":"2007","unstructured":"Dynnikov, I., Wiest, B.: On the complexity of braids. J. Eur. Math. Soc. 9(4), 801\u2013840 (2007)","journal-title":"J. Eur. Math. Soc."},{"key":"411_CR14","doi-asserted-by":"publisher","DOI":"10.1201\/9781439865699","volume-title":"Word Processing in Groups","author":"DBA Epstein","year":"1992","unstructured":"Epstein, D.B.A., Cannon, J.W., Holt, D.F., Levy, S.V.F., Paterson, M.S., Thurston, W.P.: Word Processing in Groups. Jones and Bartlett, Boston (1992)"},{"issue":"4","key":"411_CR15","doi-asserted-by":"publisher","first-page":"823","DOI":"10.1007\/s00454-013-9515-z","volume":"49","author":"J Erickson","year":"2013","unstructured":"Erickson, J., Nayyeri, A.: Tracing compressed curves in triangulated surfaces. Discrete Comput. Geom. 49(4), 823\u2013863 (2013)","journal-title":"Discrete Comput. Geom."},{"key":"411_CR16","doi-asserted-by":"crossref","unstructured":"Erickson, J., Whittlesey, K.: Transforming curves on surfaces redux. In: 24th Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans 2013), pp. 1646\u20131655. SIAM, Philadelphia (2013)","DOI":"10.1137\/1.9781611973105.118"},{"key":"411_CR17","unstructured":"Hagenah, Ch.: Gleichungen mit regul\u00e4ren Randbedingungen \u00fcber freien Gruppen. PhD thesis, Universt\u00e4t Stuttgart (2000). https:\/\/elib.uni-stuttgart.de\/handle\/11682\/2469"},{"key":"411_CR18","series-title":"Chicago Lectures in Mathematics","volume-title":"Topics in Geometric Group Theory","author":"P de la Harpe","year":"2000","unstructured":"de la Harpe, P.: Topics in Geometric Group Theory. Chicago Lectures in Mathematics, University of Chicago Press, Chicago (2000)"},{"issue":"2","key":"411_CR19","first-page":"185","volume":"46","author":"J Hass","year":"1999","unstructured":"Hass, J., Lagarias, J.C., Pippenger, N.: The computational complexity of knot and link problems. J.\u00a0ACM 46(2), 185\u2013211 (1999)","journal-title":"J.\u00a0ACM"},{"issue":"1","key":"411_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00454-002-2707-6","volume":"29","author":"J Hass","year":"2003","unstructured":"Hass, J., Snoeyink, J., Thurston, W.P.: The size of spanning disks for polygonal curves. Discrete Comput. Geom. 29(1), 1\u201317 (2003)","journal-title":"Discrete Comput. Geom."},{"key":"411_CR21","volume-title":"Algebraic Topology","author":"A Hatcher","year":"2002","unstructured":"Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002)"},{"key":"411_CR22","unstructured":"Hempel, J.: $$3$$-Manifolds. AMS Chelsea Publishing, vol. 349. American Mathematical Society, Providence (2004)"},{"key":"411_CR23","unstructured":"Holt, D., Lohrey, M., Schleimer, S.: Compressed decision problems in hyperbolic groups. In: 36th International Symposium on Theoretical Aspects of Computer Science (Berlin 2019). Leibniz International Proceedings in Informatics, vol. 126, #\u00a037. Leibniz-Zent. Inform., Wadern (2019)"},{"issue":"1","key":"411_CR24","doi-asserted-by":"publisher","first-page":"61","DOI":"10.4310\/jdg\/1090503053","volume":"65","author":"W Jaco","year":"2003","unstructured":"Jaco, W., Rubinstein, J.H.: $$0$$-efficient triangulations of $$3$$-manifolds. J. Differ. Geom. 65(1), 61\u2013168 (2003)","journal-title":"J. Differ. Geom."},{"issue":"3","key":"411_CR25","first-page":"358","volume":"39","author":"W Jaco","year":"1995","unstructured":"Jaco, W., Tollefson, J.L.: Algorithms for the complete decomposition of a closed $$3$$-manifold. Ill. J. Math. 39(3), 358\u2013406 (1995)","journal-title":"Ill. J. Math."},{"issue":"1","key":"411_CR26","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)","journal-title":"Pacific J. Math."},{"issue":"3","key":"411_CR27","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)","journal-title":"Discrete Comput. Geom."},{"key":"411_CR28","doi-asserted-by":"crossref","unstructured":"Lackenby, M.: Algorithms in $$3$$-manifold theory (2020). arXiv:2002.02179","DOI":"10.4310\/SDG.2020.v25.n1.a5"},{"key":"411_CR29","doi-asserted-by":"publisher","first-page":"#107796","DOI":"10.1016\/j.aim.2021.107796","volume":"387","author":"M Lackenby","year":"2021","unstructured":"Lackenby, M.: The efficient certification of knottedness and Thurston norm. Adv. Math. 387, #107796 (2021)","journal-title":"Adv. Math."},{"key":"411_CR30","doi-asserted-by":"crossref","unstructured":"Lazarus, F., Rivaud, J.: On the homotopy test on surfaces. In: 53rd Annual IEEE Symposium on Foundations of Computer Science (New Brunswick 2012), pp. 440\u2013449. IEEE Computer Society, Los Alamitos (2012)","DOI":"10.1109\/FOCS.2012.12"},{"key":"411_CR31","unstructured":"L\u00f6ffler, M., Lubiw, A., Schleimer, S., Wolf Chambers, E.M. (eds.): Computation in low-dimensional geometry and topology (Dagstuhl Seminar 19352). Dagstuhl Reports 9(8), 84\u2013112 (2019)"},{"issue":"5","key":"411_CR32","doi-asserted-by":"publisher","first-page":"1210","DOI":"10.1137\/S0097539704445950","volume":"35","author":"M Lohrey","year":"2006","unstructured":"Lohrey, M.: Word problems and membership problems on compressed words. SIAM J. Comput. 35(5), 1210\u20131240 (2006)","journal-title":"SIAM J. Comput."},{"key":"411_CR33","doi-asserted-by":"crossref","unstructured":"Lohrey, M.: The Compressed Word Problem for Groups. SpringerBriefs in Mathematics. Springer, New York (2014)","DOI":"10.1007\/978-1-4939-0748-9"},{"key":"411_CR34","unstructured":"Matveev, S.: Algorithmic Topology and Classification of $$3$$-Manifolds. Algorithms and Computation in Mathematics. vol.\u00a09. Springer, Berlin (2007)"},{"key":"411_CR35","unstructured":"de Mesmay, A., Rieck, Y., Sedgwick, E., Tancer, M.: The unbearable hardness of unknotting. In: 35th International Symposium on Computational Geometry (Portland 2019). Leibniz International Proceedings in Informatics, vol. 129, #\u00a049. Leibniz-Zent. Inform., Wadern (2019)"},{"key":"411_CR36","series-title":"Johns Hopkins Studies in the Mathematical Sciences","doi-asserted-by":"publisher","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"B Mohar","year":"2001","unstructured":"Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore (2001)"},{"key":"411_CR37","doi-asserted-by":"publisher","first-page":"96","DOI":"10.2307\/1969769","volume":"56","author":"EE Moise","year":"1952","unstructured":"Moise, E.E.: Affine structures in $$3$$-manifolds. V. The triangulation theorem and Hauptvermutung. Ann. Math. 56, 96\u2013114 (1952)","journal-title":"Ann. Math."},{"key":"411_CR38","doi-asserted-by":"crossref","unstructured":"Schaefer, M., Sedgwick, E., \u0160tefankovi\u0107, D.: Algorithms for normal curves and surfaces. In: Computing and Combinatorics (Singapore 2002). Lecture Notes in Computer Science, vol. 2387, pp. 370\u2013380. Springer, Berlin (2002)","DOI":"10.1007\/3-540-45655-4_40"},{"key":"411_CR39","unstructured":"Schaefer, M., Sedgwick, E., \u0160tefankovi\u0107, D.: Computing Dehn twists and geometric intersection numbers in polynomial time. In: 20th Canadian Conference on Computational Geometry (Montreal 2008), pp. 111\u2013114 (2008)"},{"issue":"4","key":"411_CR40","doi-asserted-by":"publisher","first-page":"741","DOI":"10.4171\/CMH\/142","volume":"83","author":"S Schleimer","year":"2008","unstructured":"Schleimer, S.: Polynomial-time word problems. Comment. Math. Helv. 83(4), 741\u2013765 (2008)","journal-title":"Comment. Math. Helv."},{"key":"411_CR41","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/BF01210965","volume":"76","author":"H Schubert","year":"1961","unstructured":"Schubert, H.: Bestimmung der Primfaktorzerlegung von Verkettungen. Math. Z. 76, 116\u2013148 (1961)","journal-title":"Math. Z."},{"key":"411_CR42","doi-asserted-by":"crossref","unstructured":"Stillwell, J.: Classical Topology and Combinatorial Group Theory. Graduate Texts in Mathematics, vol. 72. Springer, New York (1993)","DOI":"10.1007\/978-1-4612-4372-4"},{"key":"411_CR43","doi-asserted-by":"publisher","first-page":"272","DOI":"10.2307\/1970574","volume":"88","author":"F Waldhausen","year":"1968","unstructured":"Waldhausen, F.: The word problem in fundamental groups of sufficiently large irreducible $$3$$-manifolds. Ann. Math. 88, 272\u2013280 (1968)","journal-title":"Ann. Math."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00411-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-022-00411-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00411-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,12]],"date-time":"2023-08-12T19:02:32Z","timestamp":1691866952000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-022-00411-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,18]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["411"],"URL":"https:\/\/doi.org\/10.1007\/s00454-022-00411-x","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2022,7,18]]},"assertion":[{"value":"3 June 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 March 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 April 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 July 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}