{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:30:29Z","timestamp":1750307429791,"version":"3.41.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2010,8,1]],"date-time":"2010-08-01T00:00:00Z","timestamp":1280620800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["J1-7218P1-0297"],"award-info":[{"award-number":["J1-7218P1-0297"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2010,8]]},"abstract":"<jats:p>A cycle on a combinatorial surface is tight if it as short as possible in its (free) homotopy class. We describe an algorithm to compute a single tight, noncontractible, essentially simple cycle on a given orientable combinatorial surface in<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>log<jats:italic>n<\/jats:italic>) time. The only method previously known for this problem was to compute the globally shortest noncontractible or nonseparating cycle in<jats:italic>O<\/jats:italic>(min{<jats:italic>g<\/jats:italic><jats:sup>3<\/jats:sup>,<jats:italic>n<\/jats:italic>},<jats:italic>n<\/jats:italic>log<jats:italic>n<\/jats:italic>) time, where<jats:italic>g<\/jats:italic>is the genus of the surface. As a consequence, we can compute the shortest cycle freely homotopic to a chosen boundary cycle in<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>log<jats:italic>n<\/jats:italic>) time, a tight octagonal decomposition in<jats:italic>O<\/jats:italic>(<jats:italic>gn<\/jats:italic>log<jats:italic>n<\/jats:italic>) time, and a shortest contractible cycle enclosing a nonempty set of faces in<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>log<jats:sup>2<\/jats:sup><jats:italic>n<\/jats:italic>) time.<\/jats:p>","DOI":"10.1145\/1824777.1824781","type":"journal-article","created":{"date-parts":[[2010,9,2]],"date-time":"2010-09-02T13:14:24Z","timestamp":1283433264000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Finding one tight cycle"],"prefix":"10.1145","volume":"6","author":[{"given":"Sergio","family":"Cabello","sequence":"first","affiliation":[{"name":"University of Ljubljana, Slovenia and IMFM"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matt","family":"Devos","sequence":"additional","affiliation":[{"name":"Simon Fraser University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeff","family":"Erickson","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bojan","family":"Mohar","sequence":"additional","affiliation":[{"name":"Simon Fraser University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,9,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523189"},{"volume-title":"Proceedings of the 18th Symposium on Discrete Algorithms (SODA'07)","author":"Cabello S.","key":"e_1_2_1_2_1","unstructured":"Cabello , S. and Chambers , E. W . 2007. Multiple source shortest paths in a genus g graph . In Proceedings of the 18th Symposium on Discrete Algorithms (SODA'07) . 89--97. Cabello, S. and Chambers, E. W. 2007. Multiple source shortest paths in a genus g graph. In Proceedings of the 18th Symposium on Discrete Algorithms (SODA'07). 89--97."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1292-5"},{"volume-title":"Proceedings of the 15th Symposium on Discrete Algorithms (SODA'04)","author":"Chalermsook P.","key":"e_1_2_1_4_1","unstructured":"Chalermsook , P. , Fakcharoenphol , J. , and Nanongkai , D . 2004. A deterministic near-linear time algorithm for finding minimum cuts in planar graphs . In Proceedings of the 15th Symposium on Discrete Algorithms (SODA'04) . 828--829. Chalermsook, P., Fakcharoenphol, J., and Nanongkai, D. 2004. A deterministic near-linear time algorithm for finding minimum cuts in planar graphs. In Proceedings of the 15th Symposium on Discrete Algorithms (SODA'04). 828--829."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137918"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109580"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 11th International Symposium on Graph Drawing. Lecture Notes in Computer Science","volume":"2912","author":"Colin de Verdi\u00e8re","unstructured":"Colin de Verdi\u00e8re , \u00c9. and Lazarus, F . 2004. Optimal pants decompositions and shortest homotopic cycles on an orientable surface . In Proceedings of the 11th International Symposium on Graph Drawing. Lecture Notes in Computer Science , vol. 2912 . Springer, 478--490. Colin de Verdi\u00e8re, \u00c9. and Lazarus, F. 2004. Optimal pants decompositions and shortest homotopic cycles on an orientable surface. In Proceedings of the 11th International Symposium on Graph Drawing. Lecture Notes in Computer Science, vol. 2912. Springer, 478--490."},{"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","volume-title":"Proceedings of the 14th Symposium on Discrete Algorithms (SODA'03)","author":"Eppstein D.","year":"2003","unstructured":"Eppstein , D. 2003 . Dynamic generators of topologically embedded graphs . In Proceedings of the 14th Symposium on Discrete Algorithms (SODA'03) . 599--608. Eppstein, D. 2003. Dynamic generators of topologically embedded graphs. In Proceedings of the 14th Symposium on Discrete Algorithms (SODA'03). 599--608."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-003-2948-z"},{"volume-title":"Proceedings of the 16th Symposium on Discrete Algorithms (SODA'03)","author":"Erickson J.","key":"e_1_2_1_11_1","unstructured":"Erickson , J. and Whittlesey , K . 2005. Greedy optimal homotopy and homology generators . In Proceedings of the 16th Symposium on Discrete Algorithms (SODA'03) . 1038--1046. Erickson, J. and Whittlesey, K. 2005. Greedy optimal homotopy and homology generators. In Proceedings of the 16th Symposium on Discrete Algorithms (SODA'03). 1038--1046."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216064"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02772960"},{"key":"e_1_2_1_14_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_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250848"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137919"},{"key":"e_1_2_1_17_1","volume-title":"Algebraic Topology: An Introduction","author":"Massey W. S.","year":"1967","unstructured":"Massey , W. S. 1967 . Algebraic Topology: An Introduction . Springer Verlag . Massey, W. S. 1967. Algebraic Topology: An Introduction. Springer Verlag."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Mohar B. and Thomassen C. 2001. Graphs on Surfaces. Johns Hopkins University Press Baltimore. Mohar B. and Thomassen C. 2001. Graphs on Surfaces. Johns Hopkins University Press Baltimore.","DOI":"10.56021\/9780801866890"},{"volume-title":"Classical Topology and Combinatorial Group Theory","author":"Stillwell J.","key":"e_1_2_1_19_1","unstructured":"Stillwell , J. 1993. Classical Topology and Combinatorial Group Theory . Springer-Verlag , Berlin . Stillwell, J. 1993. Classical Topology and Combinatorial Group Theory. Springer-Verlag, Berlin."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1824777.1824781","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1824777.1824781","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:39:53Z","timestamp":1750246793000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1824777.1824781"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,8]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,8]]}},"alternative-id":["10.1145\/1824777.1824781"],"URL":"https:\/\/doi.org\/10.1145\/1824777.1824781","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2010,8]]},"assertion":[{"value":"2009-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-09-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}