{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:08:18Z","timestamp":1750306098766,"version":"3.41.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,1,23]],"date-time":"2018-01-23T00:00:00Z","timestamp":1516665600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["PP00P2-138948, 200020-138230"],"award-info":[{"award-number":["PP00P2-138948, 200020-138230"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000782","name":"European Science Foundation","doi-asserted-by":"publisher","award":["Eurocores Project GIG\/11\/E023"],"award-info":[{"award-number":["Eurocores Project GIG\/11\/E023"]}],"id":[{"id":"10.13039\/501100000782","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["Advanced Grant No. 267165,Marie SkBodowska-Curie Action COFUND grant 291734"],"award-info":[{"award-number":["Advanced Grant No. 267165,Marie SkBodowska-Curie Action COFUND grant 291734"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2018,2,28]]},"abstract":"<jats:p>\n            We show that the following algorithmic problem is decidable: given a 2-dimensional simplicial complex, can it be embedded (topologically, or equivalently, piecewise linearly) in R\n            <jats:sup>3<\/jats:sup>\n            ? By a known reduction, it suffices to decide the embeddability of a given triangulated 3-manifold\n            <jats:italic>X<\/jats:italic>\n            into the 3-sphere\n            <jats:italic>S<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            . The main step, which allows us to simplify\n            <jats:italic>X<\/jats:italic>\n            and recurse, is in proving that if\n            <jats:italic>X<\/jats:italic>\n            can be embedded in\n            <jats:italic>S<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            , then there is also an embedding in which\n            <jats:italic>X<\/jats:italic>\n            has a\n            <jats:italic>short meridian<\/jats:italic>\n            , that is, an essential curve in the boundary of\n            <jats:italic>X<\/jats:italic>\n            bounding a disk in\n            <jats:italic>S<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            \\\n            <jats:italic>X<\/jats:italic>\n            with length bounded by a computable function of the number of tetrahedra of\n            <jats:italic>X<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/3078632","type":"journal-article","created":{"date-parts":[[2018,1,26]],"date-time":"2018-01-26T13:05:50Z","timestamp":1516971950000},"page":"1-49","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Embeddability in the 3-Sphere Is Decidable"],"prefix":"10.1145","volume":"65","author":[{"given":"Ji\u0159\u00ed","family":"Matou\u0161ek","sequence":"first","affiliation":[{"name":"Charles University and ETH Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Sedgwick","sequence":"additional","affiliation":[{"name":"DePaul University, Chicago, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Tancer","sequence":"additional","affiliation":[{"name":"Charles University, Praha, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1494-0568","authenticated-orcid":false,"given":"Uli","family":"Wagner","sequence":"additional","affiliation":[{"name":"IST Austria, Klosterneuburg, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,1,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.2140\/gt.2010.14.585"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00208-012-0802-4"},{"key":"e_1_2_1_3_1","volume-title":"Geometry and Topology Down Under. Contemp. Math.","volume":"597","author":"Bachman D.","unstructured":"D. Bachman , R. Derby-Talbot , and E. Sedgwick . 2013. Almost normal surfaces with boundary . In Geometry and Topology Down Under. Contemp. Math. , Vol. 597 . Amer. Math. Soc., Providence, RI, 177--194. D. Bachman, R. Derby-Talbot, and E. Sedgwick. 2013. Almost normal surfaces with boundary. In Geometry and Topology Down Under. Contemp. Math., Vol. 597. Amer. Math. Soc., Providence, RI, 177--194."},{"key":"e_1_2_1_4_1","volume-title":"An alternative proof that 3-manifolds can be triangulated. Ann. of Math. (2) 69","author":"Bing R. H.","year":"1959","unstructured":"R. H. Bing . 1959. An alternative proof that 3-manifolds can be triangulated. Ann. of Math. (2) 69 ( 1959 ), 37--65. R. H. Bing. 1959. An alternative proof that 3-manifolds can be triangulated. Ann. of Math. (2) 69 (1959), 37--65."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1090\/coll\/040"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9900-0"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2597629"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/120899029"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1353\/ajm.2014.0027"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"B. Farb and D. Margalit. 2011. A Primer on Mapping Class Groups. Princeton University Press Princeton NJ.  B. Farb and D. Margalit. 2011. A Primer on Mapping Class Groups. Princeton University Press Princeton NJ.","DOI":"10.1515\/9781400839049"},{"key":"e_1_2_1_11_1","volume-title":"On the imbedding of polyhedra in 3-space. Ann. of Math. (2) 49","author":"Fox R. H.","year":"1948","unstructured":"R. H. Fox . 1948. On the imbedding of polyhedra in 3-space. Ann. of Math. (2) 49 ( 1948 ), 462--470. R. H. Fox. 1948. On the imbedding of polyhedra in 3-space. Ann. of Math. (2) 49 (1948), 462--470."},{"key":"e_1_2_1_12_1","unstructured":"J. Geelen T. Huynh and R. B. Richter. 2013. Explicit bounds for graph minors. (2013). Preprint http:\/\/arxiv.org\/abs\/1305.1451.  J. Geelen T. Huynh and R. B. Richter. 2013. Explicit bounds for graph minors. (2013). Preprint http:\/\/arxiv.org\/abs\/1305.1451."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1989-0965210-7"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322156"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02559591"},{"key":"e_1_2_1_16_1","unstructured":"J. Hass and G. Kuperberg. 2012. The Complexity of Recognizing the 3-Sphere. Report 24\/2012. (2012).  J. Hass and G. Kuperberg. 2012. The Complexity of Recognizing the 3-Sphere. Report 24\/2012. (2012)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/301970.301971"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1982.99.373"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02395059"},{"volume-title":"of Math. Studies","author":"Hempel J.","key":"e_1_2_1_20_1","unstructured":"J. Hempel . 1976. 3-Manifolds. Ann. of Math. Studies , Vol. 86 . Princeton University Press , Princeton, N. J. J. Hempel. 1976. 3-Manifolds. Ann. of Math. Studies, Vol. 86. Princeton University Press, Princeton, N. J."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10711-007-9210-4"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1090\/cbms\/043"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0040-9383(84)90039-9"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218216509006987"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.4310\/jdg\/1090503053"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0040-9383(02)00083-6"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1215\/ijm\/1255986385"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-013-9159-7"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2014.01.007"},{"key":"e_1_2_1_30_1","volume-title":"A polynomial upper bound on Reidemeister moves. Ann. of Math. (2) 182, 2","author":"Lackenby M.","year":"2015","unstructured":"M. Lackenby . 2015. A polynomial upper bound on Reidemeister moves. Ann. of Math. (2) 182, 2 ( 2015 ), 491--564. M. Lackenby. 2015. A polynomial upper bound on Reidemeister moves. Ann. of Math. (2) 182, 2 (2015), 491--564."},{"key":"e_1_2_1_31_1","unstructured":"M. Lackenby. 2016. The efficient certification of knottedness and Thurston norm. (2016). Preprint arXiv:1604.00290.  M. Lackenby. 2016. The efficient certification of knottedness and Thurston norm. (2016). Preprint arXiv:1604.00290."},{"key":"e_1_2_1_32_1","unstructured":"M. Lackenby. 2016. Elementary knot theory. (2016). Preprint https:\/\/arxiv.org\/abs\/1604.03778.  M. Lackenby. 2016. Elementary knot theory. (2016). Preprint https:\/\/arxiv.org\/abs\/1604.03778."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-09-09878-5"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-016-1294-9"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.4171\/JEMS\/252"},{"volume-title":"Using the Borsuk--Ulam theorem","author":"Matou\u0161ek J.","key":"e_1_2_1_36_1","unstructured":"J. Matou\u0161ek . 2003. Using the Borsuk--Ulam theorem . Springer-Verlag , Berlin . J. Matou\u0161ek. 2003. Using the Borsuk--Ulam theorem. Springer-Verlag, Berlin."},{"key":"e_1_2_1_37_1","volume-title":"Classification of sufficiently large 3-manifolds. Uspekhi Mat. Nauk 52, 5(317)","author":"Matveev S. V.","year":"1997","unstructured":"S. V. Matveev . 1997. Classification of sufficiently large 3-manifolds. Uspekhi Mat. Nauk 52, 5(317) ( 1997 ), 147--174. Translation in Russian Math. Surveys 52 (1997), no. 5, 1029--1055. S. V. Matveev. 1997. Classification of sufficiently large 3-manifolds. Uspekhi Mat. Nauk 52, 5(317) (1997), 147--174. Translation in Russian Math. Surveys 52 (1997), no. 5, 1029--1055."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.4310\/MRL.2005.v12.n6.a6"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100043279"},{"key":"e_1_2_1_40_1","first-page":"1","article-title":"A new proof for the invariance of the homology groups of a complex (in Greek)","volume":"22","author":"Papakyriakopoulos C.","year":"1943","unstructured":"C. Papakyriakopoulos . 1943 . A new proof for the invariance of the homology groups of a complex (in Greek) . Bull. Soc. Math. Gr\u00e8ce 22 (1943), 1 -- 154 . C. Papakyriakopoulos. 1943. A new proof for the invariance of the homology groups of a complex (in Greek). Bull. Soc. Math. Gr\u00e8ce 22 (1943), 1--154.","journal-title":"Bull. Soc. Math. Gr\u00e8ce"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(10)80005-7"},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"C. P. Rourke and B. J. Sanderson. 1972. Introduction to Piecewise-Linear Topology. Ergebnisse der Mathematik und ihrer Grenzgebiete Vol. 69. Springer-Verlag New York.  C. P. Rourke and B. J. Sanderson. 1972. Introduction to Piecewise-Linear Topology. Ergebnisse der Mathematik und ihrer Grenzgebiete Vol. 69. Springer-Verlag New York.","DOI":"10.1007\/978-3-642-81735-9"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-9078-6_54"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1090\/pspum\/082\/2768660"},{"key":"e_1_2_1_45_1","first-page":"57","article-title":"Die eindeutige Zerlegbarkeit eines Knotens in Primknoten","volume":"3","author":"Schubert H.","year":"1949","unstructured":"H. Schubert . 1949 . Die eindeutige Zerlegbarkeit eines Knotens in Primknoten . S.-B. Heidelberger Akad. Wiss. Math.-Nat. Kl. 3 (1949), 57 -- 104 . H. Schubert. 1949. Die eindeutige Zerlegbarkeit eines Knotens in Primknoten. S.-B. Heidelberger Akad. Wiss. Math.-Nat. Kl. 3 (1949), 57--104.","journal-title":"S.-B. Heidelberger Akad. Wiss. Math.-Nat. Kl."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02305012"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-99-02296-5"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.4310\/MRL.1994.v1.n5.a9"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.topol.2011.04.001"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-016-9855-6"},{"key":"e_1_2_1_51_1","unstructured":"R. Zentner. 2016. Integer homology 3-spheres admit irreducible representations in . (2016). Preprint arXiv:1605.08530.  R. Zentner. 2016. Integer homology 3-spheres admit irreducible representations in . (2016). Preprint arXiv:1605.08530."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3078632","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3078632","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:31Z","timestamp":1750217431000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3078632"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,23]]},"references-count":51,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,2,28]]}},"alternative-id":["10.1145\/3078632"],"URL":"https:\/\/doi.org\/10.1145\/3078632","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2018,1,23]]},"assertion":[{"value":"2014-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}