{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:21:07Z","timestamp":1758273667664,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,6,9]],"date-time":"2017-06-09T00:00:00Z","timestamp":1496966400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,6,9]],"date-time":"2017-06-09T00:00:00Z","timestamp":1496966400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["P140104246"],"award-info":[{"award-number":["P140104246"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["REA 291734"],"award-info":[{"award-number":["REA 291734"]}],"id":[{"id":"10.13039\/501100000781","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":[[2017,12]]},"DOI":"10.1007\/s00454-017-9900-0","type":"journal-article","created":{"date-parts":[[2017,6,9]],"date-time":"2017-06-09T13:30:35Z","timestamp":1497015035000},"page":"871-888","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Finding Non-orientable Surfaces in 3-Manifolds"],"prefix":"10.1007","volume":"58","author":[{"given":"Benjamin A.","family":"Burton","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7301-3799","authenticated-orcid":false,"given":"Arnaud","family":"de Mesmay","sequence":"additional","affiliation":[]},{"given":"Uli","family":"Wagner","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,6,9]]},"reference":[{"issue":"9","key":"9900_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. Amer. Math. Soc. 358(9), 3821\u20133850 (2006)","journal-title":"Trans. Amer. Math. Soc."},{"key":"9900_CR2","doi-asserted-by":"crossref","unstructured":"Bachman, D., Derby-Talbot, R., Sedgwick, E.: Computing Heegaard genus is NP-hard. arXiv:1606.01553 (2016)","DOI":"10.1007\/978-3-319-44479-6_3"},{"key":"9900_CR3","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/BF01389793","volume":"7","author":"GE Bredon","year":"1969","unstructured":"Bredon, G.E., Wood, J.W.: Non-orientable surfaces in orientable $$3$$-manifolds. Invent. Math. 7, 83\u2013110 (1969)","journal-title":"Invent. Math."},{"issue":"1","key":"9900_CR4","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."},{"key":"9900_CR5","doi-asserted-by":"crossref","unstructured":"Burton, B.A., Ozlen, M.: Computing the crosscap number of a knot using integer programming and normal surfaces. ACM Trans. Math. Software 39(1), 4:1\u20134:18 (2012)","DOI":"10.1145\/2382585.2382589"},{"issue":"2","key":"9900_CR6","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/BF01190680","volume":"59","author":"W End","year":"1992","unstructured":"End, W.: Nonorientable surfaces in 3-manifolds. Arch. Math. (Basel) 59(2), 173\u2013185 (1992)","journal-title":"Arch. Math. (Basel)"},{"issue":"3\u20134","key":"9900_CR7","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/BF02559591","volume":"105","author":"W Haken","year":"1961","unstructured":"Haken, W.: Theorie der Normalfl\u00e4chen: Ein Isotopiekriterium f\u00fcr den Kreisknoten. Acta Math. 105(3\u20134), 245\u2013375 (1961)","journal-title":"Acta Math."},{"key":"9900_CR8","doi-asserted-by":"crossref","unstructured":"Hass, J.: What is an almost normal surface. arXiv:1208.0568v1 (2012)","DOI":"10.1090\/conm\/597\/11777"},{"key":"9900_CR9","unstructured":"Hass, J., Kuperberg, G.: The complexity of recognizing the 3-sphere. In: Triangulations. Oberwolfach Reports, vol. 9(2), pp. 1425\u20131426. European Mathematical Society, Z\u00fcrich (2012)"},{"issue":"2","key":"9900_CR10","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1145\/301970.301971","volume":"46","author":"J Hass","year":"1999","unstructured":"Hass, J., Lagarias, J.C., Pippenger, N.: The computational complexity of knot and link problems. J. ACM 46(2), 185\u2013211 (1999)","journal-title":"J. ACM"},{"key":"9900_CR11","unstructured":"Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge. http:\/\/www.math.cornell.edu\/~hatcher\/ (2002)"},{"key":"9900_CR12","unstructured":"Hatcher, A.: Notes on basic 3-manifold topology. https:\/\/www.math.cornell.edu\/~hatcher\/3M\/3Mdownloads.html (2007)"},{"key":"9900_CR13","doi-asserted-by":"crossref","unstructured":"Hempel, J.: 3-Manifolds. AMS Chelsea Publishing, Providence (2004) (Reprint of the 1976 original)","DOI":"10.1090\/chel\/349"},{"issue":"10","key":"9900_CR14","doi-asserted-by":"publisher","first-page":"1753","DOI":"10.1016\/j.topol.2009.03.002","volume":"156","author":"M Iwakura","year":"2009","unstructured":"Iwakura, M., Hayashi, C.: Non-orientable fundamental surfaces in lens spaces. Topol. Appl. 156(10), 1753\u20131766 (2009)","journal-title":"Topol. Appl."},{"issue":"2","key":"9900_CR15","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0040-9383(84)90039-9","volume":"23","author":"W Jaco","year":"1984","unstructured":"Jaco, W., Oertel, U.: An algorithm to decide if a 3-manifold is a Haken manifold. Topology 23(2), 195\u2013209 (1984)","journal-title":"Topology"},{"issue":"91","key":"9900_CR16","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(91), 61\u2013168 (2003)","journal-title":"J. Differ. Geom."},{"key":"9900_CR17","doi-asserted-by":"crossref","unstructured":"Jaco, W.H., Shalen, P.B.: Seifert Fibered Spaces in 3-Manifolds, Memoirs of the American Mathematical Society, vol. 21(220). American Mathematical Society, Providence (1979)","DOI":"10.1090\/memo\/0220"},{"key":"9900_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0085406","volume-title":"Homotopy Equivalence of 3-Manifolds with Boundaries. Lecture Notes in Mathematics","author":"K Johannson","year":"1979","unstructured":"Johannson, K.: Homotopy Equivalence of 3-Manifolds with Boundaries. Lecture Notes in Mathematics, vol. 761. Springer, Berlin (1979)"},{"key":"9900_CR19","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1090\/S0002-9947-1978-0506621-2","volume":"244","author":"PK Kim","year":"1978","unstructured":"Kim, P.K.: Some 3-manifolds which admit Klein bottles. Trans. Am. Math. Soc. 244, 299\u2013312 (1978)","journal-title":"Trans. Am. Math. Soc."},{"key":"9900_CR20","first-page":"248","volume":"28","author":"H Kneser","year":"1929","unstructured":"Kneser, H.: Geschlossene Fl\u00e4chen in dreidimensionalen Mannigfaltigkeiten. Jahresbericht Math. Verein. 28, 248\u2013259 (1929)","journal-title":"Jahresbericht Math. Verein."},{"key":"9900_CR21","unstructured":"Kuperberg, G.: Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization. arXiv:1508.06720 (2015)"},{"key":"9900_CR22","unstructured":"Lackenby, M.: The efficient certification of knottedness and Thurston norm. arXiv:1604.00290 (2016)"},{"key":"9900_CR23","doi-asserted-by":"crossref","unstructured":"Lackenby, M.: Some conditionally hard problems on links and 3-manifolds. arXiv:1602.08427 (2016)","DOI":"10.1007\/s00454-017-9905-8"},{"issue":"1","key":"9900_CR24","doi-asserted-by":"publisher","first-page":"439","DOI":"10.2140\/gt.2015.19.439","volume":"19","author":"AS Levine","year":"2015","unstructured":"Levine, A.S., Ruberman, D., Strle, S.: Nonorientable surfaces in homology cobordisms. Geom. Topol. 19(1), 439\u2013494 (2015)","journal-title":"Geom. Topol."},{"issue":"1","key":"9900_CR25","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/s00222-006-0009-y","volume":"167","author":"T Li","year":"2007","unstructured":"Li, T.: Heegaard surfaces and measured laminations. I: The Waldhausen conjecture. Invent. Math. 167(1), 135\u2013177 (2007)","journal-title":"Invent. Math."},{"issue":"2","key":"9900_CR26","doi-asserted-by":"publisher","first-page":"1029","DOI":"10.2140\/gt.2011.15.1029","volume":"15","author":"T Li","year":"2011","unstructured":"Li, T.: An algorithm to determine the Heegaard genus of a 3-manifold. Geom. Topol. 15(2), 1029\u20131106 (2011)","journal-title":"Geom. Topol."},{"key":"9900_CR27","doi-asserted-by":"crossref","unstructured":"Matou\u0161ek, J., Sedgwick, E., Tancer, M., Wagner, U.: Embeddability in the 3-sphere is decidable. In: Proceedings of the Thirtieth Annual Symposium on Computational Geometry (SOCG\u201914), pp. 78\u201384. ACM, New York (2014)","DOI":"10.1145\/2582112.2582137"},{"key":"9900_CR28","doi-asserted-by":"crossref","unstructured":"Matou\u0161ek, J., Tancer, M., Wagner, U.: Hardness of embedding simplicial complexes in $$\\mathbb{R}^d$$. J. Eur. Math. Soc. (JEMS) 13(2), 259\u2013295 (2011)","DOI":"10.4171\/JEMS\/252"},{"key":"9900_CR29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-05102-3","volume-title":"Algorithmic Topology and Classification of 3-Manifolds. Algorithms and Computation in Mathematics","author":"S Matveev","year":"2003","unstructured":"Matveev, S.: Algorithmic Topology and Classification of 3-Manifolds. Algorithms and Computation in Mathematics, vol. 9. Springer, Berlin (2003)"},{"issue":"1","key":"9900_CR30","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(1), 96\u2013114 (1952)","journal-title":"Ann. Math."},{"issue":"1","key":"9900_CR31","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0166-8641(96)00013-2","volume":"72","author":"R Rannard","year":"1996","unstructured":"Rannard, R.: Incompressible surfaces in Seifert fibered spaces. Topol. Appl. 72(1), 19\u201330 (1996)","journal-title":"Topol. Appl."},{"key":"9900_CR32","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1090\/S0002-9947-1979-0531972-6","volume":"251","author":"JH Rubinstein","year":"1979","unstructured":"Rubinstein, J.H.: On 3-manifolds that have finite fundamental group and contain Klein bottles. Trans. Am. Math. Soc. 251, 129\u2013137 (1979)","journal-title":"Trans. Am. Math. Soc."},{"issue":"2","key":"9900_CR33","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1090\/S0002-9947-1982-0645327-7","volume":"270","author":"JH Rubinstein","year":"1982","unstructured":"Rubinstein, J.H.: Nonorientable surfaces in some non-Haken 3-manifolds. Trans. Amer. Math. Soc. 270(2), 503\u2013524 (1982)","journal-title":"Trans. Amer. Math. Soc."},{"key":"9900_CR34","unstructured":"Rubinstein, J.H.: An algorithm to recognize the $$3$$-sphere. In: Proceedings of the International Congress of Mathematicians, vol. 1, 2 (Z\u00fcrich, 1994), pp. 601\u2013611. Birkh\u00e4user, Basel (1995)"},{"key":"9900_CR35","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing (STOC\u201978), pp. 216\u2013226. ACM, New York (1978)","DOI":"10.1145\/800133.804350"},{"key":"9900_CR36","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1090\/pspum\/082\/2768660","volume-title":"Low-Dimensional and Symplectic Topology. Proceedings of Symposia in Pure Mathematics","author":"S Schleimer","year":"2011","unstructured":"Schleimer, S.: Sphere recognition lies in NP. In: Usher, M. (ed.) Low-Dimensional and Symplectic Topology. Proceedings of Symposia in Pure Mathematics, vol. 82, pp. 183\u2013213. American Mathematical Society, Providence (2011)"},{"issue":"2","key":"9900_CR37","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1007\/BF02110742","volume":"56","author":"AB Skopenkov","year":"1994","unstructured":"Skopenkov, A.B.: Geometric proof of Neuwirth\u2019s theorem on the construction of 3-manifolds from 2-demensional polyhedra. Math. Notes 56(2), 827\u2013829 (1994)","journal-title":"Math. Notes"},{"key":"9900_CR38","first-page":"248","volume-title":"Surveys in Contemporary Mathematics. London Mathematical Society Lecture Note Series","author":"AB Skopenkov","year":"2008","unstructured":"Skopenkov, A.B.: Embedding and knotting of manifolds in Euclidean spaces. In: Young, N., Choi, Y. (eds.) Surveys in Contemporary Mathematics. London Mathematical Society Lecture Note Series, vol. 347, pp. 248\u2013342. Cambridge University Press, Cambridge (2008)"},{"issue":"4","key":"9900_CR39","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1016\/0196-6774(89)90006-0","volume":"10","author":"C Thomassen","year":"1989","unstructured":"Thomassen, C.: The graph genus problem is NP-complete. J. Algorithms 10(4), 568\u2013576 (1989)","journal-title":"J. Algorithms"},{"issue":"5","key":"9900_CR40","doi-asserted-by":"publisher","first-page":"613","DOI":"10.4310\/MRL.1994.v1.n5.a9","volume":"1","author":"A Thompson","year":"1994","unstructured":"Thompson, A.: Thin position and the recognition problem for $${S}^3$$. Math. Res. Lett. 1(5), 613\u2013630 (1994)","journal-title":"Math. Res. Lett."},{"key":"9900_CR41","doi-asserted-by":"crossref","unstructured":"Wagner, U.: Minors in random and expanding hypergraphs. In: Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry (SCG\u201911), pp. 351\u2013360. ACM, New York (2011)","DOI":"10.1145\/1998196.1998256"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-017-9900-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-017-9900-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-017-9900-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,29]],"date-time":"2022-07-29T12:01:38Z","timestamp":1659096098000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-017-9900-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,9]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["9900"],"URL":"https:\/\/doi.org\/10.1007\/s00454-017-9900-0","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2017,6,9]]},"assertion":[{"value":"1 September 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 February 2017","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2017","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 June 2017","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}