{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:32:31Z","timestamp":1750307551260,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2010,3,1]],"date-time":"2010-03-01T00:00:00Z","timestamp":1267401600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2010,3]]},"abstract":"<jats:p>We give a polynomial-time algorithm to find a shortest contractible cycle (i.e., a closed walk without repeated vertices) in a graph embedded in a surface. This answers a question posed by Hutchinson. In contrast, we show that finding a shortest contractible cycle through a given vertex is NP-hard. We also show that finding a shortest separating cycle in an embedded graph is NP-hard. This answers a question posed by Mohar and Thomassen.<\/jats:p>","DOI":"10.1145\/1721837.1721840","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Finding shortest contractible and shortest separating cycles in embedded graphs"],"prefix":"10.1145","volume":"6","author":[{"given":"Sergio","family":"Cabello","sequence":"first","affiliation":[{"name":"University of Ljubljana and IMFM, Ljubljana, Slovenia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,4,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109691"},{"volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'07)","author":"Cabello S.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","article-title":"Finding one tight cycle. ACM","author":"Cabello S.","year":"2008","journal-title":"Trans. Algor. To appear. http:\/\/www.imfm.si\/preprint\/PDF\/01047.pdf (preprint)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1292-5"},{"volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04)","author":"Chalermsook P.","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.10.010"},{"volume-title":"Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'06)","author":"Colin de Verdi\u00e8re","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-004-1150-2"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1255443.1255446"},{"volume-title":"Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP'00)","series-title":"Lecture Notes in Computer Science","author":"Djidjev H.","key":"e_1_2_1_10_1"},{"volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'03)","year":"2003","author":"Eppstein D.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-003-2948-z"},{"volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'03)","author":"Erickson J.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1976.233819"},{"key":"e_1_2_1_15_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company.   Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company."},{"key":"e_1_2_1_16_1","unstructured":"Hatcher A. 2001. Algebraic Topology. Cambridge University Press. http:\/\/www. math.cornell.edu\/~hatcher\/.  Hatcher A. 2001. Algebraic Topology. Cambridge University Press. http:\/\/www. math.cornell.edu\/~hatcher\/."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1493"},{"key":"e_1_2_1_18_1","first-page":"317","article-title":"Polynomially bounded minimization problems that are hard to approximate","volume":"1","author":"Kann V.","year":"1994","journal-title":"Nordic J. Comput."},{"volume":"2025","volume-title":"Methods and Models. Lecture Notes in Computer Science","author":"Kaufmann M.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137919"},{"volume-title":"Algebraic Topology: An Introduction","year":"1967","author":"Massey W. S.","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","unstructured":"Mohar B. and Thomassen C. 2001. Graphs on Surfaces. Johns Hopkins University Press Baltimore MD.  Mohar B. and Thomassen C. 2001. Graphs on Surfaces. Johns Hopkins University Press Baltimore MD."},{"volume":"12","volume-title":"Planar Graph Drawing. Lecture Notes Series on Computing","author":"Nishizeki T.","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11425-005-0012-6"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Stillwell J. 1993. Classical Topology and Combinatorial Group Theory. Springer New York.  Stillwell J. 1993. Classical Topology and Combinatorial Group Theory. Springer New York.","DOI":"10.1007\/978-1-4612-4372-4"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90115-G"},{"key":"e_1_2_1_27_1","unstructured":"Thomassen C. 1991. Recent results on graph embeddings. In Graph Theory Combinatorics and Applications Y. Alavi G. Chartrand O. R. Ollerman and A. J. Schwenk Eds. John Wiley and Sons 1093--1103.  Thomassen C. 1991. Recent results on graph embeddings. In Graph Theory Combinatorics and Applications Y. Alavi G. Chartrand O. R. Ollerman and A. J. Schwenk Eds. John Wiley and Sons 1093--1103."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1721837.1721840","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1721837.1721840","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:23:38Z","timestamp":1750249418000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1721837.1721840"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,3]]}},"alternative-id":["10.1145\/1721837.1721840"],"URL":"https:\/\/doi.org\/10.1145\/1721837.1721840","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2010,3]]},"assertion":[{"value":"2008-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-04-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}