{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T04:12:37Z","timestamp":1776831157035,"version":"3.51.2"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T00:00:00Z","timestamp":1667174400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-14-08763, CCF-15-13816, CCF-15-46392, and IIS-14-08846"],"award-info":[{"award-number":["CCF-14-08763, CCF-15-13816, CCF-15-46392, and IIS-14-08846"]}]},{"name":"U.S.-Israel Binational Science Foundation","award":["W911NF-15-1-0408, and 2012\/229"],"award-info":[{"award-number":["W911NF-15-1-0408, and 2012\/229"]}]},{"name":"French ANR","award":["ANR-18-CE40-0004-01 (FOCAL), ANR-17-CE40-0033 (SoS), ANR-16-CE40-0009-01 (GATO) and ANR-19-CE40-0014 (MINMAX)"],"award-info":[{"award-number":["ANR-18-CE40-0004-01 (FOCAL), ANR-17-CE40-0033 (SoS), ANR-16-CE40-0009-01 (GATO) and ANR-19-CE40-0014 (MINMAX)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>\n            We prove the first polynomial bound on the number of\n            <jats:italic>monotonic<\/jats:italic>\n            homotopy moves required to tighten a collection of closed curves on any compact orientable surface, where the number of crossings in the curve is not allowed to increase at any time during the process. The best known upper bound before was exponential, which can be obtained by combining the algorithm of De Graaf and Schrijver [\n            <jats:italic>J. Comb. Theory Ser. B<\/jats:italic>\n            , 1997] together with an exponential upper bound on the number of possible surface maps. To obtain the new upper bound, we apply tools from hyperbolic geometry, as well as operations in graph drawing algorithms\u2014the cluster and pipe expansions\u2014to the study of curves on surfaces.\n          <\/jats:p>\n          <jats:p>\n            As corollaries, we present two efficient algorithms for curves and graphs on surfaces. First, we provide a polynomial-time algorithm to convert any given multicurve on a surface into minimal position. Such an algorithm only existed for single closed curves, and it is known that previous techniques do not generalize to the multicurve case. Second, we provide a polynomial-time algorithm to reduce any\n            <jats:italic>k<\/jats:italic>\n            -terminal plane graph (and more generally, surface graph) using degree-1 reductions, series-parallel reductions, and \u0394\n            <jats:italic>Y<\/jats:italic>\n            -transformations for arbitrary integer\n            <jats:italic>k<\/jats:italic>\n            . Previous algorithms only existed in the planar setting when\n            <jats:italic>k<\/jats:italic>\n            \u2264 4, and all of them rely on extensive case-by-case analysis based on different values of\n            <jats:italic>k<\/jats:italic>\n            . Our algorithm makes use of the connection between electrical transformations and homotopy moves and thus solves the problem in a unified fashion.\n          <\/jats:p>","DOI":"10.1145\/3558097","type":"journal-article","created":{"date-parts":[[2022,9,9]],"date-time":"2022-09-09T13:46:58Z","timestamp":1662731218000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Tightening Curves on Surfaces Monotonically with Applications"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6714-7988","authenticated-orcid":false,"given":"Hsien-Chih","family":"Chang","sequence":"first","affiliation":[{"name":"Dartmouth College, Hanover, NH, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7301-3799","authenticated-orcid":false,"given":"Arnaud","family":"de Mesmay","sequence":"additional","affiliation":[{"name":"LIGM, CNRS, ENPC, ESIEE Paris, Univ Gustave Eiffel Marne-la-Vall\u00e9e, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,11,11]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.8.3.311"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9918-3"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.20"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1926-1501346-5"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.2307\/1968399"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.2307\/2944327"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.5555\/1379789.1379792"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1112\/blms.12057"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(86)90065-8"},{"key":"e_1_3_2_11_2","volume-title":"Tightening Curves and Graphs on Surfaces","author":"Chang Hsien-Chih","year":"2018","unstructured":"Hsien-Chih Chang. 2018. Tightening Curves and Graphs on Surfaces. Ph.D. dissertation. University of Illinois at Urbana-Champaign."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2019.25"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9907-6"},{"key":"e_1_3_2_14_2","first-page":"121","volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Chang Hsien-Chih","year":"2018","unstructured":"Hsien-Chih Chang, Jeff Erickson, Arnaud de Mesmay, David Letscher, Saul Schleimer, Eric Sedgwick, Dylan Thurston, and Stephan Tillmann. 2018. Untangling curves on surfaces via local moves. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms. 121\u2013135."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.110"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)E0111-3"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/090761653"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02566413"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.12.090"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(98)10087-3"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1754"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01456932"},{"key":"e_1_3_2_23_2","first-page":"1728","volume-title":"Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Demasi Lino","year":"2015","unstructured":"Lino Demasi and Bojan Mohar. 2015. Four terminal planar delta-wye reducibility via rooted \\( K_{2,4} \\) minors. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms. 1728\u20131742."},{"key":"e_1_3_2_24_2","volume-title":"Proceedings of the 33rd International Symposium on Computational Geometry (SoCG\u201917)","author":"Despr\u00e9 Vincent","year":"2017","unstructured":"Vincent Despr\u00e9 and Francis Lazarus. 2017. Computing the geometric intersection number of curves. In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG\u201917). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_25_2","first-page":"599","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Eppstein David","year":"2003","unstructured":"David Eppstein. 2003. Dynamic generators of topologically embedded graphs. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. 599\u2013608."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-003-2948-z"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.88"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.118"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1515\/9781400839049"},{"key":"e_1_3_2_30_2","volume-title":"I. A Lagrangian Relaxation Method for Testing the Infeasibility of Certain VLSI Routing Problems. II. Efficient Reduction of Planar Networks For Solving Certain Combinatorial Problems","author":"Feo Thomas A.","year":"1985","unstructured":"Thomas A. Feo. 1985. I. A Lagrangian Relaxation Method for Testing the Infeasibility of Certain VLSI Routing Problems. II. Efficient Reduction of Planar Networks For Solving Certain Combinatorial Problems. Ph. D. Dissertation. University of California Berkeley. Retrieved from http:\/\/search.proquest.com\/docview\/303364161."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.41.3.572"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-04414-5_16"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3502264"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1006\/aima.1993.1056"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.5555\/919265"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.20399"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1006\/aama.1993.1015"},{"key":"e_1_3_2_38_2","first-page":"125","volume-title":"Handbook of Discrete and Computational Geometry (3rd ed.)","author":"Goodman Jacob E.","year":"2017","unstructured":"Jacob E. Goodman and Stefan Felsner. 2017. Pseudoline arrangements. In Handbook of Discrete and Computational Geometry (3rd ed.), Csaba D. Toth, Joseph O\u2019Rourke, and Jacob E. Goodman (Eds.). Chapman and Hall\/CRC, 125\u2013157."},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M1163153"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.2307\/1971486"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02772960"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1016\/0040-9383(94)90033-7"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.2140\/gtm.1999.2.201"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2017.44"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022429530062"},{"issue":"12","key":"e_1_3_2_46_2","first-page":"413","article-title":"Equivalence of triangles and three-pointed stars in conducting networks","volume":"34","author":"Kennelly Arthur Edwin","year":"1899","unstructured":"Arthur Edwin Kennelly. 1899. Equivalence of triangles and three-pointed stars in conducting networks. Electric. World Eng. 34, 12 (1899), 413\u2013414.","journal-title":"Electric. World Eng."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.12"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1137\/0111058"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61896-3"},{"issue":"7","key":"e_1_3_2_50_2","first-page":"1079","article-title":"An algorithm for the solution of a linear system by  \\( \\Delta \\) -Y transformations","volume":"79","author":"Nakahara Hiroyuki","year":"1996","unstructured":"Hiroyuki Nakahara and Hiromitsu Takahashi. 1996. An algorithm for the solution of a linear system by \\( \\Delta \\) -Y transformations. IEICE Trans. Fundam. Electron., Commun. Comput. Sci. E79-A, 7 (1996), 1079\u20131088.","journal-title":"IEICE Trans. Fundam. Electron., Commun. Comput. Sci."},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.2140\/agt.2001.1.349"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.5555\/1379828.1379837"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.5555\/933313"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.121.081601"},{"key":"e_1_3_2_55_2","series-title":"Ergebnisse der Mathematik und ihrer Grenzgebiete","volume-title":"Knotentheorie","author":"Reidemeister Kurt","year":"1932","unstructured":"Kurt Reidemeister. 1932. Knotentheorie. Ergebnisse der Mathematik und ihrer Grenzgebiete, Vol. 1. Springer."},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01166556"},{"key":"e_1_3_2_57_2","first-page":"75","article-title":"\u00dcber Geraden in allgemeiner Lage.","volume":"12","author":"Ringel Gerhard","year":"1957","unstructured":"Gerhard Ringel. 1957. \u00dcber Geraden in allgemeiner Lage. Elemente der Mathematik 12 (1957), 75\u201382.","journal-title":"Elemente der Mathematik"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(92)90038-Y"},{"key":"e_1_3_2_59_2","volume-title":"The Topology of Shortest Curves in Surfaces","author":"Shepard Marc","year":"1991","unstructured":"Marc Shepard. 1991. The Topology of Shortest Curves in Surfaces. Ph. D. Dissertation. University of California, Berkeley."},{"key":"e_1_3_2_60_2","first-page":"2848","volume-title":"Proceedings of the IEEE Conference on Robotics and Automation","author":"Staffelli Ernesto","year":"2002","unstructured":"Ernesto Staffelli and Federico Thomas. 2002. Analytic formulation of the kinestatis of robot manipulators with arbitrary topology. In Proceedings of the IEEE Conference on Robotics and Automation. 2848\u20132855."},{"issue":"12","key":"e_1_3_2_61_2","first-page":"1","article-title":"Polyeder und Raumeinteilungen","author":"Steinitz Ernst","year":"1916","unstructured":"Ernst Steinitz. 1916. Polyeder und Raumeinteilungen. Enzyklop\u00e4die der mathematischen Wissenschaften mit Einschluss ihrer Anwendungen III.AB, 12 (1916), 1\u2013139.","journal-title":"Enzyklop\u00e4die der mathematischen Wissenschaften mit Einschluss ihrer Anwendungen"},{"key":"e_1_3_2_62_2","series-title":"Grundlehren der mathematischen Wissenschaften","volume-title":"Vorlesungen \u00fcber die Theorie der Polyeder: unter Einschlu\u00df der Elemente der Topologie","author":"Steinitz Ernst","year":"1934","unstructured":"Ernst Steinitz and Hans Rademacher. 1934. Vorlesungen \u00fcber die Theorie der Polyeder: unter Einschlu\u00df der Elemente der Topologie. Grundlehren der mathematischen Wissenschaften, Vol. 41. Springer-Verlag. Reprinted 1976."},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4372-4"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0080456800090633"},{"key":"e_1_3_2_65_2","unstructured":"Tiffani Traver. 2014. Trigonometry in the Hyperbolic Plane. https:\/\/www.whitman.edu\/Documents\/Academics\/Mathematics\/2014\/brewert.pdf."},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130202"},{"issue":"2","key":"e_1_3_2_67_2","first-page":"155","article-title":"On the graphs of knots","volume":"9","author":"Yajima Takeshi","year":"1957","unstructured":"Takeshi Yajima and Shin\u2019ichi Kinoshita. 1957. On the graphs of knots. Osaka Math. J. 9, 2 (1957), 155\u2013163.","journal-title":"Osaka Math. J."},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2005.08.009"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3558097","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3558097","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3558097","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:32Z","timestamp":1750182572000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3558097"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,31]]},"references-count":67,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3558097"],"URL":"https:\/\/doi.org\/10.1145\/3558097","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,31]]},"assertion":[{"value":"2020-02-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-07-25","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}