{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:06:11Z","timestamp":1750309571368,"version":"3.41.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,3,13]],"date-time":"2025-03-13T00:00:00Z","timestamp":1741824000000},"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":[[2025,4,30]]},"abstract":"<jats:p>\n            In this article, we consider a transformation of\n            <jats:italic>k<\/jats:italic>\n            disjoint paths in a graph. For a graph and a pair of\n            <jats:italic>k<\/jats:italic>\n            disjoint paths\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal{P}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            and\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal{Q}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            connecting the same set of terminal pairs, we aim to determine whether\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal{P}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            can be transformed to\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal{Q}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            by repeatedly replacing one path with another path so that the intermediates are also\n            <jats:italic>k<\/jats:italic>\n            disjoint paths. The problem is called\n            <jats:sc>Disjoint Paths Reconfiguration<\/jats:sc>\n            . We first show that\n            <jats:sc>Disjoint Paths Reconfiguration<\/jats:sc>\n            is\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathsf{PSPACE}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -complete even when\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(k=2\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . On the other hand, we prove that, when the graph is embedded on a plane and all paths in\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal{P}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            and\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal{Q}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            connect the boundaries of two faces,\n            <jats:sc>Disjoint Paths Reconfiguration<\/jats:sc>\n            can be solved in polynomial time. The algorithm is based on a topological characterization for rerouting curves on a plane using the algebraic intersection number. We also consider a transformation of disjoint\n            <jats:italic>s<\/jats:italic>\n            -\n            <jats:italic>t<\/jats:italic>\n            paths as a variant. We show that the disjoint\n            <jats:italic>s<\/jats:italic>\n            -\n            <jats:italic>t<\/jats:italic>\n            paths reconfiguration problem in planar graphs can be determined in polynomial time, while the problem is\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathsf{PSPACE}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -complete in general.\n          <\/jats:p>","DOI":"10.1145\/3715694","type":"journal-article","created":{"date-parts":[[2025,1,29]],"date-time":"2025-01-29T16:33:20Z","timestamp":1738168400000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Rerouting Planar Curves and Disjoint Paths"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9912-6898","authenticated-orcid":false,"given":"Takehiro","family":"Ito","sequence":"first","affiliation":[{"name":"Graduate School of Information Sciences, Tohoku University, Sendai, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6794-3543","authenticated-orcid":false,"given":"Yuni","family":"Iwamasa","sequence":"additional","affiliation":[{"name":"Graduate School of Informatics, Kyoto University, Kyoto, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3918-3479","authenticated-orcid":false,"given":"Naonori","family":"Kakimura","sequence":"additional","affiliation":[{"name":"Faculty of Science and Technology, Keio University, Minato-ku, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9478-7307","authenticated-orcid":false,"given":"Yusuke","family":"Kobayashi","sequence":"additional","affiliation":[{"name":"Research Institute for Mathematical Sciences, Kyoto University, Kyoto, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1607-8665","authenticated-orcid":false,"given":"Shun-Ichi","family":"Maezawa","sequence":"additional","affiliation":[{"name":"Department of Information Science, College of Humanities and Sciences, Nihon University, Chiyoda, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3223-0153","authenticated-orcid":false,"given":"Yuta","family":"Nozaki","sequence":"additional","affiliation":[{"name":"Faculty of Environment and Information Sciences, Yokohama National University, Yokohama, Japan and WPI-SKCM, Hiroshima University, Higashihiroshima, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9826-7074","authenticated-orcid":false,"given":"Yoshio","family":"Okamoto","sequence":"additional","affiliation":[{"name":"Graduate School of Informatics and Engineering, The University of Electro-Communications, Chofu, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3118-0086","authenticated-orcid":false,"given":"Kenta","family":"Ozeki","sequence":"additional","affiliation":[{"name":"Faculty of Environment and Information Sciences, Yokohama National University,  Yokohama, Japan"}]}],"member":"320","published-online":{"date-parts":[[2025,3,13]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"crossref","first-page":"815","DOI":"10.1016\/j.jctb.2016.10.001","article-title":"Irrelevant vertices for the planar disjoint paths problem","volume":"122","author":"Adler Isolde","year":"2017","unstructured":"Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M Thilikos. 2017. Irrelevant vertices for the planar disjoint paths problem. Journal of Combinatorial Theory, Series B 122 (2017), 815\u2013843. https:\/\/doi.org\/10.1016\/j.jctb.2016.10.001","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"e_1_3_2_3_2","first-page":"1","volume-title":"2019 IFIP Networking Conference (Networking \u201919)","author":"Akhoondian Amiri Saeed","year":"2019","unstructured":"Saeed Akhoondian Amiri, Szymon Dudycz, Mahmoud Parham, Stefan Schmid, and Sebastian Wiederrecht. 2019. On polynomial-time congestion-free software-defined network updates. In 2019 IFIP Networking Conference (Networking \u201919). IEEE, 1\u20139. https:\/\/doi.org\/10.23919\/IFIPNetworking.2019.8816833"},{"key":"e_1_3_2_4_2","first-page":"143:1","volume-title":"45th International Colloquium on Automata, Languages, and Programming (ICALP \u201918)","author":"Saeed Akhoondian Amiri","year":"2018","unstructured":"Saeed Akhoondian Amiri, Szymon Dudycz, Stefan Schmid, and Sebastian Wiederrecht. 2018. Congestion-free rerouting of flows on DAGs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP \u201918). Ioannis Chatzigiannakis, Christos Kaklamanis, D\u00e1niel Marx, and Donald Sannella (Eds.), Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 143:1\u2013143:13. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.143"},{"issue":"10","key":"e_1_3_2_5_2","doi-asserted-by":"crossref","first-page":"2938","DOI":"10.1016\/j.disc.2018.07.007","article-title":"Reconfiguration graphs of shortest paths","volume":"341","author":"Asplund John","year":"2018","unstructured":"John Asplund, Kossi D. Edoh, Ruth Haas, Yulia Hristova, Beth Novick, and Brett Werner. 2018. Reconfiguration graphs of shortest paths. Discrete Mathematics 341, 10 (2018), 2938\u20132948. https:\/\/doi.org\/10.1016\/j.disc.2018.07.007","journal-title":"Discrete Mathematics"},{"issue":"1","key":"e_1_3_2_6_2","doi-asserted-by":"crossref","first-page":"111640","DOI":"10.1016\/j.disc.2019.111640","article-title":"Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles","volume":"343","author":"Asplund John","year":"2020","unstructured":"John Asplund and Brett Werner. 2020. Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles. Discrete Mathematics 343, 1 (2020), 111640. https:\/\/doi.org\/10.1016\/j.disc.2019.111640","journal-title":"Discrete Mathematics"},{"key":"e_1_3_2_7_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2013.09.012","article-title":"The complexity of rerouting shortest paths","volume":"510","author":"Bonsma Paul S.","year":"2013","unstructured":"Paul S. Bonsma. 2013. The complexity of rerouting shortest paths. Theoretical Computer Science 510 (2013), 1\u201312. https:\/\/doi.org\/10.1016\/j.tcs.2013.09.012","journal-title":"Theoretical Computer Science"},{"key":"e_1_3_2_8_2","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/j.dam.2016.05.024","article-title":"Rerouting shortest paths in planar graphs","volume":"231","author":"Bonsma Paul S.","year":"2017","unstructured":"Paul S. Bonsma. 2017. Rerouting shortest paths in planar graphs. Discrete Applied Mathematics 231 (2017), 95\u2013112. https:\/\/doi.org\/10.1016\/j.dam.2016.05.024","journal-title":"Discrete Applied Mathematics"},{"key":"e_1_3_2_9_2","first-page":"227","volume-title":"23rd Annual European Symposium on Algorithms (ESA) (Lecture Notes in Computer Science, Vol. 9294)","author":"Borradaile Glencora","year":"2015","unstructured":"Glencora Borradaile, Amir Nayyeri, and Farzad Zafarani. 2015. Towards single face shortest vertex-disjoint paths in undirected planar graphs. In 23rd Annual European Symposium on Algorithms (ESA) (Lecture Notes in Computer Science, Vol. 9294), 227\u2013238. https:\/\/doi.org\/10.1007\/978-3-662-48350-3_20"},{"issue":"2","key":"e_1_3_2_10_2","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/0012-365X(86)90086-5","article-title":"The bandwidth problem and operations on graphs","volume":"61","author":"Chvatalova Jarmila","year":"1986","unstructured":"Jarmila Chvatalova and Jaroslav Opatrny. 1986. The bandwidth problem and operations on graphs. Discrete Mathematics 61, 2\u20133 (1986), 141\u2013150. https:\/\/doi.org\/10.1016\/0012-365X(86)90086-5","journal-title":"Discrete Mathematics"},{"issue":"2","key":"e_1_3_2_11_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1921659.1921665","article-title":"Shortest vertex-disjoint two-face paths in planar graphs","volume":"7","author":"Verdi\u00e8re \u00c9ric Colin de","year":"2011","unstructured":"\u00c9ric Colin de Verdi\u00e8re and Alexander Schrijver. 2011. Shortest vertex-disjoint two-face paths in planar graphs. ACM Transactions on Algorithms 7, 2 (2011), 1\u201312. https:\/\/doi.org\/10.1145\/1921659.1921665","journal-title":"ACM Transactions on Algorithms"},{"key":"e_1_3_2_12_2","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1109\/FOCS.2013.29","volume-title":"54th Annual IEEE Symposium on Foundations of Computer Science (FOCS \u201813)","author":"Cygan Marek","year":"2013","unstructured":"Marek Cygan, D\u00e1niel Marx, Marcin Pilipczuk, and Michal Pilipczuk. 2013. The planar directed k-vertex-disjoint paths problem is fixed-parameter tractable. In 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS \u201813), 197\u2013206. https:\/\/doi.org\/10.1109\/FOCS.2013.29"},{"key":"e_1_3_2_13_2","first-page":"19:1","volume-title":"38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS \u201818)","volume":"122","author":"Datta Samir","year":"2018","unstructured":"Samir Datta, Siddharth Iyer, Raghav Kulkarni, and Anish Mukherjee. 2018. Shortest k-disjoint paths via determinants. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS \u201818), Vol. 122, 19:1\u201319:21. https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2018.19"},{"key":"e_1_3_2_14_2","first-page":"72:1","volume-title":"32nd International Symposium on Algorithms and Computation (ISAAC \u201921)","author":"Enoch Julian","year":"2021","unstructured":"Julian Enoch, Kyle Fox, Dor Mesica, and Shay Mozes. 2021. A faster algorithm for maximum flow in directed planar graphs with vertex capacities. In 32nd International Symposium on Algorithms and Computation (ISAAC \u201921). Hee-Kap Ahn and Kunihiko Sadakane (Eds.), Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 72:1\u201372:16. https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2021.72"},{"key":"e_1_3_2_15_2","first-page":"472","volume-title":"Princeton Mathematical Series","author":"Farb Benson","year":"2012","unstructured":"Benson Farb and Dan Margalit. 2012. A Primer on Mapping Class Groups. Princeton Mathematical Series, Vol. 49. Princeton University Press, Princeton, NJ, 472 pages."},{"key":"e_1_3_2_16_2","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","article-title":"Maximal flow through a network","volume":"8","author":"Ford Lester R.","year":"1956","unstructured":"Lester R. Ford and Delbert R. Fulkerson. 1956. Maximal flow through a network. Canadian Journal of Mathematics 8 (1956), 399\u2013404. https:\/\/doi.org\/10.4153\/CJM-1956-045-5","journal-title":"Canadian Journal of Mathematics"},{"issue":"2","key":"e_1_3_2_17_2","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","article-title":"The directed subgraph homeomorphism problem","volume":"10","author":"Fortune Steven","year":"1980","unstructured":"Steven Fortune, John Hopcroft, and James Wyllie. 1980. The directed subgraph homeomorphism problem. Theoretical Computer Science 10, 2 (1980), 111\u2013121. https:\/\/doi.org\/10.1016\/0304-3975(80)90009-2","journal-title":"Theoretical Computer Science"},{"key":"e_1_3_2_18_2","first-page":"47","volume-title":"Paths, Flows, and VLSI-Layout","author":"Frank Andr\u00e1s","year":"1990","unstructured":"Andr\u00e1s Frank. 1990. Packing paths, circuits, and cuts \u2013 a survey. In Paths, Flows, and VLSI-Layout. Bernhard Korte, L. Lov\u00e1sz, Hans J. Pr\u00f6mel, and Alexand Schrijver (Eds.), Springer, 47\u2013100."},{"key":"e_1_3_2_19_2","first-page":"9758","volume-title":"36th AAAI Conference on Artificial Intelligence (AAAI \u201922)","author":"Gajjar Kshitij","year":"2022","unstructured":"Kshitij Gajjar, Agastya Vibhuti Jha, Manish Kumar, and Abhiruk Lahiri. 2022. Reconfiguring shortest paths in graphs. In 36th AAAI Conference on Artificial Intelligence (AAAI \u201922). AAAI Press, 9758\u20139766."},{"issue":"2","key":"e_1_3_2_20_2","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1002\/net.3230140204","article-title":"On multicommodity flows in planar graphs","volume":"14","author":"Hassin Refael","year":"1984","unstructured":"Refael Hassin. 1984. On multicommodity flows in planar graphs. Networks 14, 2 (1984), 225\u2013235. https:\/\/doi.org\/10.1002\/net.3230140204","journal-title":"Networks"},{"issue":"1","key":"e_1_3_2_21_2","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/j.tcs.2005.05.008","article-title":"PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation","volume":"343","author":"Hearn Robert A.","year":"2005","unstructured":"Robert A. Hearn and Erik D. Demaine. 2005. PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science 343, 1\u20132 (2005), 72\u201396. https:\/\/doi.org\/10.1016\/j.tcs.2005.05.008","journal-title":"Theoretical Computer Science"},{"issue":"12","key":"e_1_3_2_22_2","first-page":"1054","article-title":"On the complexity of reconfiguration problems","volume":"412","author":"Ito Takehiro","year":"2011","unstructured":"Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno. 2011. On the complexity of reconfiguration problems. Theoretical Computer Science 412, 12\u201314 (2011), 1054\u20131065. https:\/\/doi.org\/10.1016\/j.tcs.2010.12.005","journal-title":"Theoretical Computer Science"},{"key":"e_1_3_2_23_2","first-page":"81:1","volume-title":"50th International Colloquium on Automata, Languages, and Programming (ICALP \u201923)","author":"Ito Takehiro","year":"2023","unstructured":"Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki. 2023. Rerouting planar curves and disjoint paths. In 50th International Colloquium on Automata, Languages, and Programming (ICALP \u201923), 81:1\u201381:19. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2023.81"},{"issue":"2","key":"e_1_3_2_24_2","doi-asserted-by":"crossref","first-page":"454","DOI":"10.1007\/s10878-018-0289-3","article-title":"Reconfiguration of maximum-weight b-matchings in a graph","volume":"37","author":"Ito Takehiro","year":"2019","unstructured":"Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto. 2019. Reconfiguration of maximum-weight b-matchings in a graph. Journal of Combinatorial Optimization 37, 2 (2019), 454\u2013464. https:\/\/doi.org\/10.1007\/s10878-018-0289-3","journal-title":"Journal of Combinatorial Optimization"},{"key":"e_1_3_2_25_2","first-page":"167","volume-title":"Integration of Constraint Programming, Artificial Intelligence, and Operations Research; 20th International Conference (CPAIOR \u201823) (Lecture Notes in Computer Science, Vol. 13884)","author":"Ito Takehiro","year":"2023","unstructured":"Takehiro Ito, Jun Kawahara, Yu Nakahata, Takehide Soh, Akira Suzuki, Junichi Teruyama, and Takahisa Toda. 2023. ZDD-based algorithmic framework for solving shortest reconfiguration problems. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research; 20th International Conference (CPAIOR \u201823) (Lecture Notes in Computer Science, Vol. 13884). Andr\u00e9 A. Cir\u00e9 (Ed.), Springer, 167\u2013183. https:\/\/doi.org\/10.1007\/978-3-031-33271-5_12"},{"issue":"39","key":"e_1_3_2_26_2","doi-asserted-by":"crossref","first-page":"5205","DOI":"10.1016\/j.tcs.2011.05.021","article-title":"Shortest paths between shortest paths","volume":"412","author":"Kaminski Marcin","year":"2011","unstructured":"Marcin Kaminski, Paul Medvedev, and Martin Milanic. 2011. Shortest paths between shortest paths. Theoretical Computer Science 412, 39 (2011), 5205\u20135210. https:\/\/doi.org\/10.1016\/j.tcs.2011.05.021","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"e_1_3_2_27_2","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1007\/s00453-010-9436-7","article-title":"Maximum flow in directed planar graphs with vertex capacities","volume":"61","author":"Kaplan Haim","year":"2011","unstructured":"Haim Kaplan and Yahav Nussbaum. 2011. Maximum flow in directed planar graphs with vertex capacities. Algorithmica 61, 1 (2011), 174\u2013189. https:\/\/doi.org\/10.1007\/s00453-010-9436-7","journal-title":"Algorithmica"},{"issue":"1","key":"e_1_3_2_28_2","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","article-title":"On the computational complexity of combinatorial problems","volume":"5","author":"Karp Richard M.","year":"1975","unstructured":"Richard M. Karp. 1975. On the computational complexity of combinatorial problems. Networks 5, 1 (1975), 45\u201368. https:\/\/doi.org\/10.1002\/net.1975.5.1.45","journal-title":"Networks"},{"issue":"3","key":"e_1_3_2_29_2","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1007\/BF01240733","article-title":"Flow in planar graphs with vertex capacities","volume":"11","author":"Khuller Samir","year":"1994","unstructured":"Samir Khuller and Joseph Naor. 1994. Flow in planar graphs with vertex capacities. Algorithmica 11, 3 (1994), 200\u2013225. https:\/\/doi.org\/10.1007\/BF01240733","journal-title":"Algorithmica"},{"key":"e_1_3_2_30_2","doi-asserted-by":"crossref","first-page":"1635","DOI":"10.1109\/INFOCOM.2014.6848100","volume-title":"2014 IEEE Conference on Computer Communications (INFOCOM)","author":"Kobayashi Yusuke","year":"2014","unstructured":"Yusuke Kobayashi and Kensuke Otsuki. 2014. Max-flow min-cut theorem and faster algorithms in a circular disk failure model. In 2014 IEEE Conference on Computer Communications (INFOCOM), 1635\u20131643. https:\/\/doi.org\/10.1109\/INFOCOM.2014.6848100"},{"issue":"4","key":"e_1_3_2_31_2","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1016\/j.disopt.2010.05.002","article-title":"On shortest disjoint paths in planar graphs","volume":"7","author":"Kobayashi Yusuke","year":"2010","unstructured":"Yusuke Kobayashi and Christian Sommer. 2010. On shortest disjoint paths in planar graphs. Discrete Optimization 7, 4 (2010), 234\u2013245. https:\/\/doi.org\/10.1016\/j.disopt.2010.05.002","journal-title":"Discrete Optimization"},{"issue":"1984","key":"e_1_3_2_32_2","first-page":"129","article-title":"The complexity of wire-routing and finding minimum area layouts for arbitrary VLSI circuits","volume":"2","author":"Kramer Mark R.","year":"1984","unstructured":"Mark R. Kramer. 1984. The complexity of wire-routing and finding minimum area layouts for arbitrary VLSI circuits. Advances in Computing Research 2 (1984), 129\u2013146.","journal-title":"Advances in Computing Research"},{"issue":"3","key":"e_1_3_2_33_2","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/1061425.1061430","article-title":"The equivalence of theorem proving and the interconnection problem","volume":"5","author":"Lynch James F.","year":"1975","unstructured":"James F. Lynch. 1975. The equivalence of theorem proving and the interconnection problem. ACM SIGDA Newsletter 5, 3 (1975), 31\u201336. https:\/\/doi.org\/10.1145\/1061425.1061430","journal-title":"ACM SIGDA Newsletter"},{"key":"e_1_3_2_34_2","first-page":"245","volume-title":"3rd Scandinavian Workshop on Algorithm Theory (SWAT)","author":"McDiarmid Colin J. H.","year":"1992","unstructured":"Colin J. H. McDiarmid, Bruce A. Reed, Alexander Schrijver, and F. Bruce Shepherd. 1992. Non-interfering network flows. In 3rd Scandinavian Workshop on Algorithm Theory (SWAT), 245\u2013257. https:\/\/doi.org\/10.1007\/3-540-55706-7_21"},{"issue":"2","key":"e_1_3_2_35_2","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1006\/jctb.1994.1011","article-title":"Induced circuits in planar graphs","volume":"60","author":"McDiarmid Colin J. H.","year":"1994","unstructured":"Colin J. H. McDiarmid, Bruce A. Reed, Alexander Schrijver, and F. Bruce Shepherd. 1994. Induced circuits in planar graphs. Journal of Combinatorial Theory, Series B 60, 2 (1994), 169\u2013176. https:\/\/doi.org\/10.1006\/jctb.1994.1011","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"1927","key":"e_1_3_2_36_2","doi-asserted-by":"crossref","first-page":"96","DOI":"10.4064\/fm-10-1-96-115","article-title":"Zur allgemeinen Kurventheorie","volume":"10","author":"Menger Karl","year":"1927","unstructured":"Karl Menger. 1927. Zur allgemeinen Kurventheorie. Fundamenta Mathematicae 10 (1927), 96\u2013115.","journal-title":"Fundamenta Mathematicae"},{"issue":"4","key":"e_1_3_2_37_2","doi-asserted-by":"crossref","first-page":"52","DOI":"10.3390\/a11040052","article-title":"Introduction to Reconfiguration","volume":"11","author":"Nishimura Naomi","year":"2018","unstructured":"Naomi Nishimura. 2018. Introduction to Reconfiguration. Algorithms 11, 4 (2018), 52. https:\/\/doi.org\/10.3390\/a11040052","journal-title":"Algorithms"},{"issue":"1","key":"e_1_3_2_38_2","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/0166-218X(83)90100-2","article-title":"Multicommodity flows in graphs","volume":"6","author":"Okamura Haruko","year":"1983","unstructured":"Haruko Okamura. 1983. Multicommodity flows in graphs. Discrete Applied Mathematics 6, 1 (1983), 55\u201362. https:\/\/doi.org\/10.1016\/0166-218X(83)90100-2","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"e_1_3_2_39_2","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/S0095-8956(81)80012-3","article-title":"Multicommodity flows in planar graphs","volume":"31","author":"Okamura Haruko","year":"1981","unstructured":"Haruko Okamura and Paul D. Seymour. 1981. Multicommodity flows in planar graphs. Journal of Combinatorial Theory, Series B 31, 1 (1981), 75\u201381. https:\/\/doi.org\/10.1016\/S0095-8956(81)80012-3","journal-title":"Journal of Combinatorial Theory, Series B"},{"doi-asserted-by":"crossref","unstructured":"Kensuke Otsuki Yusuke Kobayashi and Kazuo Murota. 2016. Improved max-flow min-cut algorithms in a circular disk failure model with application to a road network. European Journal of Operational Research 248 2 (2016) 396\u2013403. https:\/\/doi.org\/10.1016\/j.ejor.2015.07.035","key":"e_1_3_2_40_2","DOI":"10.1016\/j.ejor.2015.07.035"},{"issue":"1995","key":"e_1_3_2_41_2","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/0166-218X(94)00104-L","article-title":"Rooted routing in the plane","volume":"57","author":"Reed Bruce","year":"1995","unstructured":"Bruce Reed. 1995. Rooted routing in the plane. Discrete Applied Mathematics 57 (1995), 213\u2013227. https:\/\/doi.org\/10.1016\/0166-218X(94)00104-L","journal-title":"Discrete Applied Mathematics"},{"key":"e_1_3_2_42_2","first-page":"295","volume-title":"Contemporary Mathematics","author":"Reed Bruce","year":"1993","unstructured":"Bruce Reed, Neil Robertson, Alexander Schrijver, and Paul D. Seymour. 1993. Finding disjoint trees in planar graphs in linear time. In Contemporary Mathematics 147. American Mathematical Society, 295\u2013301. https:\/\/doi.org\/10.1090\/conm\/147\/01180"},{"issue":"1","key":"e_1_3_2_43_2","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0095-8956(86)90031-6","article-title":"Graph minors. VI. Disjoint paths across a disc","volume":"41","author":"Robertson Neil","year":"1986","unstructured":"Neil Robertson and Paul D. Seymour. 1986. Graph minors. VI. Disjoint paths across a disc. Journal of Combinatorial Theory, Series B 41, 1 (1986), 115\u2013138. https:\/\/doi.org\/10.1016\/0095-8956(86)90031-6","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"2","key":"e_1_3_2_44_2","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1016\/0095-8956(88)90070-6","article-title":"Graph minors. VII. Disjoint paths on a surface","volume":"45","author":"Robertson Neil","year":"1988","unstructured":"Neil Robertson and Paul D. Seymour. 1988. Graph minors. VII. Disjoint paths on a surface. Journal of Combinatorial Theory, Series B 45, 2 (1988), 212\u2013254. https:\/\/doi.org\/10.1016\/0095-8956(88)90070-6","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"1","key":"e_1_3_2_45_2","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1006\/jctb.1995.1006","article-title":"Graph minors. XIII. The disjoint paths problem","volume":"63","author":"Robertson Neil","year":"1995","unstructured":"Neil Robertson and Paul D. Seymour. 1995. Graph minors. XIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B 63, 1 (1995), 65\u2013110. https:\/\/doi.org\/10.1006\/jctb.1995.1006","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"e_1_3_2_46_2","first-page":"439","volume-title":"Mathematics Lecture Series, Vol. 7","author":"Rolfsen Dale","year":"1990","unstructured":"Dale Rolfsen. 1990. Knots and links. Mathematics Lecture Series, Vol. 7. Publish or Perish, Inc., Houston, TX, 439 pages. Corrected reprint of the 1976 original."},{"doi-asserted-by":"crossref","unstructured":"Walter J. Savitch. 1970. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences 4 2 (1970) 177\u2013192. https:\/\/doi.org\/10.1016\/S0022-0000(70)80006-X","key":"e_1_3_2_47_2","DOI":"10.1016\/S0022-0000(70)80006-X"},{"issue":"4","key":"e_1_3_2_48_2","doi-asserted-by":"crossref","first-page":"780","DOI":"10.1137\/S0097539792224061","article-title":"Finding k disjoint paths in a directed planar graph","volume":"23","author":"Schrijver Alexander","year":"1994","unstructured":"Alexander Schrijver. 1994. Finding k disjoint paths in a directed planar graph. SIAM Journal on Computing 23, 4 (1994), 780\u2013788. https:\/\/doi.org\/10.1137\/S0097539792224061","journal-title":"SIAM Journal on Computing"},{"issue":"1980","key":"e_1_3_2_49_2","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0012-365X(80)90158-2","article-title":"Disjoint paths in graphs","volume":"29","author":"Seymour Paul D.","year":"1980","unstructured":"Paul D. Seymour. 1980. Disjoint paths in graphs. Discrete Mathematics 29 (1980), 293\u2013309. https:\/\/doi.org\/10.1016\/0012-365X(80)90158-2","journal-title":"Discrete Mathematics"},{"issue":"3","key":"e_1_3_2_50_2","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1145\/322203.322207","article-title":"A polynomial solution to the undirected two paths problem","volume":"27","author":"Shiloach Yossi","year":"1980","unstructured":"Yossi Shiloach. 1980. A polynomial solution to the undirected two paths problem. Journal of the ACM 27, 3 (1980), 445\u2013456. https:\/\/doi.org\/10.1145\/322203.322207","journal-title":"Journal of the ACM"},{"issue":"4","key":"e_1_3_2_51_2","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1007\/s11276-005-1765-0","article-title":"Finding minimum energy disjoint paths in wireless ad-hoc networks","volume":"11","author":"Srinivas Anand","year":"2005","unstructured":"Anand Srinivas and Eytan Modiano. 2005. Finding minimum energy disjoint paths in wireless ad-hoc networks. Wireless Networks 11, 4 (2005), 401\u2013417. https:\/\/doi.org\/10.1007\/s11276-005-1765-0","journal-title":"Wireless Networks"},{"issue":"10","key":"e_1_3_2_52_2","first-page":"55","article-title":"Algorithms for finding internally disjoint paths in a planar graph","volume":"72","author":"Suzuki Hitoshi","year":"1989","unstructured":"Hitoshi Suzuki, Takehiro Akama, and Takao Nishizeki. 1989. Algorithms for finding internally disjoint paths in a planar graph. Electronics and Communications in Japan (Part III: Fundamental Electronic Science) 72, 10 (1989), 55\u201367. https:\/\/doi.org\/10.1002\/ecjc.4430721006","journal-title":"Electronics and Communications in Japan (Part III: Fundamental Electronic Science)"},{"key":"e_1_3_2_53_2","first-page":"444","volume-title":"1st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Suzuki Hitoshi","year":"1990","unstructured":"Hitoshi Suzuki, Takehiro Akama, and Takao Nishizeki. 1990. Finding Steiner forests in planar graphs. In 1st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 444\u2013453."},{"issue":"1980","key":"e_1_3_2_54_2","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1016\/S0195-6698(80)80039-4","article-title":"2-linked graphs","volume":"1","author":"Thomassen Carsten","year":"1980","unstructured":"Carsten Thomassen. 1980. 2-linked graphs. European Journal of Combinatorics 1 (1980), 371\u2013378. https:\/\/doi.org\/10.1016\/S0195-6698(80)80039-4","journal-title":"European Journal of Combinatorics"},{"key":"e_1_3_2_55_2","series-title":"London Mathematical Society Lecture Note Series","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1017\/CBO9781139506748.005","volume-title":"Surveys in Combinatorics 2013","author":"Heuvel Jan van den","year":"2013","unstructured":"Jan van den Heuvel. 2013. The complexity of change. In Surveys in Combinatorics 2013. Simon R. Blackburn, Stefanie Gerke, and Mark Wildon (Eds.), London Mathematical Society Lecture Note Series, Vol. 409. Cambridge University Press, 127\u2013160. https:\/\/doi.org\/10.1017\/CBO9781139506748.005"},{"key":"e_1_3_2_56_2","first-page":"282","volume-title":"10th International Symposium on Parameterized and Exact Computation (IPEC \u201915)","author":"van der Zanden Tom C.","year":"2015","unstructured":"Tom C. van der Zanden. 2015. Parameterized complexity of graph constraint logic. In 10th International Symposium on Parameterized and Exact Computation (IPEC \u201915). Thore Husfeldt and Iyad A. Kanj (Eds.), Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 282\u2013293. https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2015.282"},{"issue":"1","key":"e_1_3_2_57_2","first-page":"27","article-title":"Max flows in planar graphs with vertex capacities","volume":"18","author":"Wang Yipu","year":"2022","unstructured":"Yipu Wang. 2022. Max flows in planar graphs with vertex capacities. ACM Transactions on Algorithms 18, 1, Article 9 (2022), 27 pages. https:\/\/doi.org\/10.1145\/3504032","journal-title":"ACM Transactions on Algorithms"},{"issue":"2018","key":"e_1_3_2_58_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jcss.2017.11.003","article-title":"Reconfiguration in bounded bandwidth and tree-depth","volume":"93","author":"Wrochna Marcin","year":"2018","unstructured":"Marcin Wrochna. 2018. Reconfiguration in bounded bandwidth and tree-depth. Journal of Computer and System Sciences 93 (2018), 1\u201310. https:\/\/doi.org\/10.1016\/j.jcss.2017.11.003","journal-title":"Journal of Computer and System Sciences"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3715694","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3715694","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:19:14Z","timestamp":1750295954000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3715694"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,13]]},"references-count":57,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,4,30]]}},"alternative-id":["10.1145\/3715694"],"URL":"https:\/\/doi.org\/10.1145\/3715694","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2025,3,13]]},"assertion":[{"value":"2024-01-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-16","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}