{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,23]],"date-time":"2026-06-23T16:56:25Z","timestamp":1782233785699,"version":"3.54.5"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T00:00:00Z","timestamp":1776729600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T00:00:00Z","timestamp":1776729600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/Y004256\/1"],"award-info":[{"award-number":["EP\/Y004256\/1"]}],"id":[{"id":"10.13039\/501100000266","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":[[2026,7]]},"abstract":"Abstract<\/jats:title>\n \n We present some algorithms that provide useful topological information about curves in surfaces. One of the main algorithms computes the geometric intersection number of two properly embedded 1-manifolds\n \n \n $$C_1$$<\/jats:tex-math>\n \n \n C<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and\n \n \n $$C_2$$<\/jats:tex-math>\n \n \n C<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n in a compact orientable surface\n S<\/jats:italic>\n . The surface\n S<\/jats:italic>\n is presented via a triangulation or a handle structure, and the 1-manifolds are given in normal form via their normal coordinates. The running time is bounded above by a polynomial function of the number of triangles in the triangulation (or the number of handles in the handle structure), and the logarithm of the weight of\n \n \n $$C_1$$<\/jats:tex-math>\n \n \n C<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and\n \n \n $$C_2$$<\/jats:tex-math>\n \n \n C<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . This algorithm represents an improvement over previous work, since its running time depends polynomially on the size of the triangulation of\n S<\/jats:italic>\n and it can deal with closed surfaces, unlike many earlier algorithms. Another algorithm, with similar bounds on its running time, can determine whether\n \n \n $$C_1$$<\/jats:tex-math>\n \n \n C<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and\n \n \n $$C_2$$<\/jats:tex-math>\n \n \n C<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n are isotopic. We also present a closely related algorithm that can be used to place a standard 1-manifold into normal form.\n <\/jats:p>","DOI":"10.1007\/s00454-026-00845-7","type":"journal-article","created":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T15:02:47Z","timestamp":1776783767000},"page":"539-588","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Some Fast Algorithms for Curves in Surfaces"],"prefix":"10.1007","volume":"76","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8264-8086","authenticated-orcid":false,"given":"Marc","family":"Lackenby","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,4,21]]},"reference":[{"issue":"9","key":"845_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":"845_CR2","unstructured":"Bell, M.C.: Simplifying triangulations. arXiv:1604.04314 (2016)"},{"key":"845_CR3","unstructured":"Bell, M.C., Webb, R.C.H.: Applications of fast triangulation simplification. arXiv:1605.03514 (2016)"},{"issue":"4","key":"845_CR4","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1145\/3558097","volume":"18","author":"H-C Chang","year":"2022","unstructured":"Chang, H.-C., de Mesmay, A.: Tightening curves on surfaces monotonically with applications. ACM Trans. Algorithms 18(4), 36 (2022)","journal-title":"ACM Trans. Algorithms"},{"key":"845_CR5","unstructured":"Despr\u00e9, V., Lazarus, F.: Computing the geometric intersection number of curves. In 33rd International Symposium on Computational Geometry, volume\u00a077 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 35, 15. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern (2017)"},{"key":"845_CR6","unstructured":"Dubois, L.: Making Multicurves Cross Minimally on Surfaces. In 32nd Annual European Symposium on Algorithms (ESA 2024), volume 308 of Leibniz International Proceedings in Informatics (LIPIcs), pages 50:1\u201350:15 (2024)"},{"key":"845_CR7","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/j.jalgebra.2021.09.010","volume":"607","author":"I Dynnikov","year":"2022","unstructured":"Dynnikov, I.: Counting intersections of normal curves. J. Algebra 607, 181\u2013231 (2022)","journal-title":"J. Algebra"},{"key":"845_CR8","unstructured":"Farb, B., Margalit, D.: A primer on mapping class groups. Princeton Mathematical Series, vol. 49. Princeton University Press, Princeton, NJ (2012)"},{"key":"845_CR9","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/BF01162369","volume":"80","author":"W Haken","year":"1962","unstructured":"Haken, W.: \u00dcber das Hom\u00f6omorphieproblem der 3-Mannigfaltigkeiten. I. Math. Z. 80, 89\u2013120 (1962)","journal-title":"I. Math. Z."},{"key":"845_CR10","doi-asserted-by":"publisher","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":"845_CR11","unstructured":"Lackenby, M., Yazdi, M.: Bounds for the number of moves between pants decompositions, and between triangulations. arXiv:2401.14233 (2024)"},{"key":"845_CR12","unstructured":"Matveev, S.: Algorithmic topology and classification of 3-manifolds, volume\u00a09 of Algorithms and Computation in Mathematics. Springer, Berlin, second edition (2007)"},{"key":"845_CR13","doi-asserted-by":"crossref","unstructured":"Schaefer, M., Sedgwick, E., \u0160tefankovi\u010d, D.: Algorithms for normal curves and surfaces. In Computing and combinatorics, volume 2387 of Lecture Notes in Comput. Sci., pages 370\u2013380. Springer, Berlin (2002)","DOI":"10.1007\/3-540-45655-4_40"},{"key":"845_CR14","unstructured":"Schaefer, M., Sedgwick, E., \u0160tefankovi\u010d, D.: Computing Dehn twists and geometric intersection numbers in polynomial time. In Proceedings of the 20th Annual Canadian Conference on Computational Geometry, CCCG 2008, 01 (2008)"},{"issue":"4","key":"845_CR15","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."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-026-00845-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-026-00845-7","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-026-00845-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,23]],"date-time":"2026-06-23T16:40:57Z","timestamp":1782232857000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-026-00845-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,21]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,7]]}},"alternative-id":["845"],"URL":"https:\/\/doi.org\/10.1007\/s00454-026-00845-7","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,21]]},"assertion":[{"value":"3 July 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 February 2026","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 March 2026","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 April 2026","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}