{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T20:57:39Z","timestamp":1775595459293,"version":"3.50.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,10,30]],"date-time":"2013-10-30T00:00:00Z","timestamp":1383091200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2014,1]]},"DOI":"10.1007\/s00454-013-9555-4","type":"journal-article","created":{"date-parts":[[2013,10,29]],"date-time":"2013-10-29T14:53:01Z","timestamp":1383058381000},"page":"171-206","source":"Crossref","is-referenced-by-count":6,"title":["Testing Graph Isotopy on Surfaces"],"prefix":"10.1007","volume":"51","author":[{"given":"\u00c9ric","family":"Colin de\u00a0Verdi\u00e8re","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arnaud","family":"de Mesmay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,10,30]]},"reference":[{"key":"9555_CR1","first-page":"643","volume-title":"IEEE Transactions on Computing","author":"J.L. Bentley","year":"1979","unstructured":"Bentley, J.L., Ottmann, Th.: Algorithms for reporting and counting geometric intersections. In: IEEE Transactions on Computing, vol. 28, pp. 643\u2013647 (1979)"},{"key":"9555_CR2","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1016\/S0196-6774(03)00090-7","volume":"49","author":"S. Bespamyatnikh","year":"2003","unstructured":"Bespamyatnikh, S.: Computing homotopic shortest paths in the plane. J. Algorithms 49, 284\u2013303 (2003)","journal-title":"J. Algorithms"},{"key":"9555_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/978-3-540-24698-5_37","volume-title":"LATIN 2004: Theoretical Informatics, the 6th Latin American Symposium","author":"S. Bespamyatnikh","year":"2004","unstructured":"Bespamyatnikh, S.: Encoding homotopy of paths in the plane. In: LATIN 2004: Theoretical Informatics, the 6th Latin American Symposium. Lecture Notes in Computer Science, vol. 2976, pp. 329\u2013338. Springer, Berlin (2004)"},{"key":"9555_CR4","first-page":"205","volume":"237","author":"R.H. Bing","year":"1978","unstructured":"Bing, R.H., Starbird, M.: Linear isotopies in E 2. Trans. Am. Math. Soc. 237, 205\u2013222 (1978)","journal-title":"Trans. Am. Math. Soc."},{"key":"9555_CR5","series-title":"Progress in Mathematics","volume-title":"Geometry and Spectra of Compact Riemann Surfaces","author":"P. Buser","year":"1992","unstructured":"Buser, P.: Geometry and Spectra of Compact Riemann Surfaces. Progress in Mathematics, vol. 106. Birkh\u00e4user, Basel (1992)"},{"key":"9555_CR6","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/s00454-003-2949-y","volume":"31","author":"S. Cabello","year":"2004","unstructured":"Cabello, S., Liu, Y., Mantler, A., Snoeyink, J.: Testing homotopy for paths in the plane. Discrete Comput. Geom. 31, 61\u201381 (2004)","journal-title":"Discrete Comput. Geom."},{"key":"9555_CR7","unstructured":"Colin de Verdi\u00e8re, \u00c9.: Raccourcissement de courbes et d\u00e9composition de surfaces. Ph.D. thesis, Universit\u00e9 Paris 7 (2003). English translation available at http:\/\/www.di.ens.fr\/~colin\/03these.html"},{"key":"9555_CR8","doi-asserted-by":"crossref","first-page":"3784","DOI":"10.1137\/090761653","volume":"39","author":"\u00c9. Colin de Verdi\u00e8re","year":"2010","unstructured":"Colin de Verdi\u00e8re, \u00c9., Erickson, J.: Tightening nonsimple paths and cycles on surfaces. SIAM J. Comput. 39, 3784\u20133813 (2010)","journal-title":"SIAM J. Comput."},{"key":"9555_CR9","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1007\/s00454-004-1150-2","volume":"33","author":"\u00c9. Colin de Verdi\u00e8re","year":"2005","unstructured":"Colin de Verdi\u00e8re, \u00c9., Lazarus, F.: Optimal system of loops on an orientable surface. Discrete Comput. Geom. 33, 507\u2013534 (2005)","journal-title":"Discrete Comput. Geom."},{"key":"9555_CR10","doi-asserted-by":"crossref","unstructured":"Colin de Verdi\u00e8re, \u00c9., Lazarus, F.: Optimal pants decompositions and shortest homotopic cycles on an orientable surface. J. ACM 54 (2007). Article 18","DOI":"10.1145\/1255443.1255446"},{"key":"9555_CR11","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1006\/jctb.1997.1754","volume":"70","author":"M. Graaf de","year":"1997","unstructured":"de Graaf, M., Schrijver, A.: Making curves minimally crossing by Reidemeister moves. J. Comb. Theory, Ser. B 70, 134\u2013156 (1997)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9555_CR12","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1006\/jcss.1998.1619","volume":"58","author":"T.K. Dey","year":"1999","unstructured":"Dey, T.K., Guha, S.: Transforming curves on surfaces. J. Comput. Syst. Sci. 58, 297\u2013325 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"9555_CR13","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1016\/j.comgeo.2006.03.003","volume":"35","author":"A. Efrat","year":"2006","unstructured":"Efrat, A., Kobourov, S.G., Lubiw, A.: Computing homotopic shortest paths efficiently. Comput. Geom. 35, 162\u2013172 (2006)","journal-title":"Comput. Geom."},{"key":"9555_CR14","first-page":"599","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"D. Eppstein","year":"2003","unstructured":"Eppstein, D.: Dynamic generators of topologically embedded graphs. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 599\u2013608 (2003)"},{"key":"9555_CR15","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF02392203","volume":"115","author":"D.B.A. Epstein","year":"1966","unstructured":"Epstein, D.B.A.: Curves on 2-manifolds and isotopies. Acta Math. 115, 83\u2013107 (1966)","journal-title":"Acta Math."},{"key":"9555_CR16","first-page":"1038","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"J. Erickson","year":"2005","unstructured":"Erickson, J., Whittlesey, K.: Greedy optimal homotopy and homology generators. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1038\u20131046 (2005)"},{"key":"9555_CR17","doi-asserted-by":"crossref","first-page":"1646","DOI":"10.1137\/1.9781611973105.118","volume-title":"Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"J. Erickson","year":"2013","unstructured":"Erickson, J., Whittlesey, K.: Transforming curves on surfaces redux. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1646\u20131655 (2013)"},{"key":"9555_CR18","doi-asserted-by":"crossref","DOI":"10.1515\/9781400839049","volume-title":"A Primer on Mapping Class Groups","author":"B. Farb","year":"2011","unstructured":"Farb, B., Margalit, D.: A Primer on Mapping Class Groups. Princeton University Press, Princeton (2011)"},{"key":"9555_CR19","doi-asserted-by":"crossref","first-page":"891","DOI":"10.1090\/S0002-9939-1966-0196724-4","volume":"17","author":"C.D. Feustel","year":"1966","unstructured":"Feustel, C.D.: Homotopic arcs are isotopic. Proc. Am. Math. Soc. 17, 891\u2013896 (1966)","journal-title":"Proc. Am. Math. Soc."},{"key":"9555_CR20","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/S0097-8493(00)00108-4","volume":"25","author":"C. Gotsman","year":"2001","unstructured":"Gotsman, C., Surazhsky, V.: Guaranteed intersection-free polygon morphing. Comput. Graph. 25, 67\u201375 (2001)","journal-title":"Comput. Graph."},{"key":"9555_CR21","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/S0166-8641(99)00063-2","volume":"105","author":"H. Hamidi-Tehrani","year":"2000","unstructured":"Hamidi-Tehrani, H.: On complexity of the word problem in braid groups and mapping class groups. Topol. Appl. 105, 237\u2013259 (2000)","journal-title":"Topol. Appl."},{"key":"9555_CR22","volume-title":"Algebraic Topology","author":"A. Hatcher","year":"2002","unstructured":"Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002). Available at http:\/\/www.math.cornell.edu\/~hatcher\/"},{"key":"9555_CR23","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0925-7721(94)90010-8","volume":"4","author":"J. Hershberger","year":"1994","unstructured":"Hershberger, J., Snoeyink, J.: Computing minimum length paths of a given homotopy class. Comput. Geom. 4, 63\u201398 (1994)","journal-title":"Comput. Geom."},{"key":"9555_CR24","series-title":"Graduate Texts in Mathematics","volume-title":"Differential Topology","author":"M.W. Hirsch","year":"1994","unstructured":"Hirsch, M.W.: Differential Topology. Graduate Texts in Mathematics, vol. 33. Springer, Berlin (1994). Corrected reprint of the 1976 original"},{"key":"9555_CR25","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/S0925-7721(99)00007-3","volume":"13","author":"L. Kettner","year":"1999","unstructured":"Kettner, L.: Using generic programming for designing a data structure for polyhedral surfaces. Comput. Geom. 13, 65\u201390 (1999)","journal-title":"Comput. Geom."},{"key":"9555_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1007\/3-540-44598-6_10","volume-title":"Advances in Cryptology\u2014CRYPTO 2000","author":"K.H. Ko","year":"2000","unstructured":"Ko, K.H., Lee, S.J., Cheon, J.H., Han, J.W., Kang, J.-s., Park, C.: New public-key cryptosystem using braid groups. In: Advances in Cryptology\u2014CRYPTO 2000. Lecture Notes in Computer Science, vol.\u00a01880, pp. 166\u2013183. Springer, Berlin (2000)"},{"key":"9555_CR27","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0040-9383(84)90013-2","volume":"23","author":"Y. Ladegaillerie","year":"1984","unstructured":"Ladegaillerie, Y.: Classes d\u2019isotopie de plongements de 1-complexes dans les surfaces. Topology 23, 303\u2013311 (1984)","journal-title":"Topology"},{"key":"9555_CR28","first-page":"440","volume-title":"Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"F. Lazarus","year":"2012","unstructured":"Lazarus, F., Rivaud, J.: On the homotopy test on surfaces. In: Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 440\u2013449 (2012)"},{"key":"9555_CR29","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0095-8956(82)90033-8","volume":"32","author":"S. Lins","year":"1982","unstructured":"Lins, S.: Graph-encoded maps. J. Comb. Theory, Ser. B 32, 171\u2013181 (1982)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9555_CR30","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/j.endm.2008.06.007","volume":"31","author":"A. Lubiw","year":"2008","unstructured":"Lubiw, A., Petrick, M.: Morphing planar graph drawings with bent edges. Electron. Notes Discrete Math. 31, 45\u201348 (2008)","journal-title":"Electron. Notes Discrete Math."},{"key":"9555_CR31","doi-asserted-by":"crossref","first-page":"303","DOI":"10.2307\/2118637","volume":"142","author":"L. Mosher","year":"1995","unstructured":"Mosher, L.: Mapping class groups are automatic. Ann. Math. 142, 303\u2013384 (1995)","journal-title":"Ann. Math."},{"key":"9555_CR32","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/BF01166556","volume":"64","author":"G. Ringel","year":"1956","unstructured":"Ringel, G.: Teilungen der Ebene durch Geraden oder topologische Geraden. Math. Z. 64, 79\u2013102 (1956)","journal-title":"Math. Z."},{"key":"9555_CR33","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-4372-4","volume-title":"Classical Topology and Combinatorial Group Theory","author":"J. Stillwell","year":"1993","unstructured":"Stillwell, J.: Classical Topology and Combinatorial Group Theory, 2nd edn. Springer, New York (1993)","edition":"2"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-013-9555-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-013-9555-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-013-9555-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,31]],"date-time":"2019-07-31T12:33:39Z","timestamp":1564576419000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-013-9555-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10,30]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["9555"],"URL":"https:\/\/doi.org\/10.1007\/s00454-013-9555-4","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,10,30]]}}}