{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,21]],"date-time":"2026-09-21T21:08:54Z","timestamp":1790024934166,"version":"4.0.1"},"reference-count":40,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-18-CE40-0025-01"],"award-info":[{"award-number":["ANR-18-CE40-0025-01"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-19-CE48-0016"],"award-info":[{"award-number":["ANR-19-CE48-0016"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001655","name":"Deutscher Akademischer Austauschdienst","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001655","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>We devise a constant-factor approximation algorithm for the maximization version of the edge-disjoint paths problem if the supply graph together with the demand edges forms a planar graph. By planar duality, this is equivalent to packing cuts in a planar graph such that each cut contains exactly one demand edge. We also show that the natural linear programming relaxations have constant integrality gap, yielding an approximate max-multiflow min-multicut theorem.<\/jats:p>","DOI":"10.1137\/20m1319401","type":"journal-article","created":{"date-parts":[[2021,4,13]],"date-time":"2021-04-13T09:25:58Z","timestamp":1618305958000},"page":"752-769","source":"Crossref","is-referenced-by-count":6,"title":["An Approximation Algorithm for Fully Planar Edge-Disjoint Paths"],"prefix":"10.1137","volume":"35","author":[{"given":"Chien-Chung","family":"Huang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mathieu","family":"Mari","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Claire","family":"Mathieu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kevin","family":"Schewior","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jens","family":"Vygen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,4,13]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"M. Andrews, J. Chuzhoy, S. Khanna, and L. Zhang,\n                      Hardness of the undirected edge-disjoint paths problem with congestion\n                      , in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2015, pp. 226-244.","DOI":"10.1109\/SFCS.2005.41"},{"key":"atypb2","unstructured":"Y. Aumann and Y. Rabani,\n                      Improved bounds for all optical routing\n                      , in Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1995, pp. 567-576."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.03.009"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a007"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2008.01.009"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"J. Chuzhoy,\n                      Routing in undirected graphs with constant congestion\n                      , in Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), 2012, pp. 855-874.","DOI":"10.1145\/2213977.2214054"},{"key":"atypb7","unstructured":"J. Chuzhoy and D. H. K. Kim,\n                      On approximating node-disjoint paths in grids\n                      , in Proceedings of the Workshop on Approximation, Randomization, and Combinatorial Optimization (APPROX), LIPIcs. Leibniz Int. Proc. Inform. 40, N. Garg, K. Jansen, A. Rao, and J. D. P. Rolim, eds., Wadern, Germany, 2015, pp. 187-211."},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"J. Chuzhoy, D. H. K. Kim, and S. Li,\n                      Improved approximation for node-disjoint paths in planar graphs\n                      , in Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), D. Wichs and Y. Mansour, eds., 2016, pp. 556-569.","DOI":"10.1145\/2897518.2897538"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"J. Chuzhoy, D. H. K. Kim, and R. Nimavat,\n                      New hardness results for routing on disjoint paths\n                      , in Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC), H. Hatami, P. McKenzie, and V. King, eds., 2017, pp. 86-99.","DOI":"10.1145\/3055399.3055411"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"J. Chuzhoy, D. H. K. Kim, and R. Nimavat,\n                      Almost polynomial hardness of node-disjoint paths in grids\n                      , in Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC), 2018, pp. 1220-1233.","DOI":"10.1145\/3188745.3188772"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2011.05.025"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580113"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0063-7"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90009-2"},{"key":"atypb15","first-page":"47","author":"Frank A.","year":"1990","journal-title":"Berlin"},{"key":"atypb16","first-page":"213","author":"Frank A.","year":"1996","journal-title":"Hungary"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"N. Garg, N. Kumar, and A. Seb\u00f6,\n                      Integer plane multiflow maximisation: Flow-cut gap and one-quarter-approximation\n                      , in Proceedings of the 21st International Conference on Integer Programming and Combinatorial Optimization (IPCO), Lecture Notes in Comput. Sci. 12125, D. Bienstock and G. Zambelli, eds., Springer, Cham, 2020, pp. 144-157,https:\/\/doi.org\/10.1007\/978-3-030-45771-6_12.","DOI":"10.1007\/978-3-030-45771-6_12"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793243016"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523685"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"atypb22","first-page":"273","volume":"1","author":"Guan M.","year":"1960","journal-title":"Chinese Math."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170004"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1002\/net.1975.5.1.45"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1145\/2438645.2438648"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581198"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00078-9"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/BF01902352"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(76)90049-6"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1007\/BF01202792"},{"key":"atypb31","unstructured":"B. Mohar and C. Thomassen,\n                      Graphs on Surfaces\n                      , Johns Hopkins Stud. Math. Sci., Johns Hopkins University Press, Baltimore, MD, 2001."},{"key":"atypb32","first-page":"261","author":"Naves G.","year":"2009","journal-title":"Berlin"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1750"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"atypb35","unstructured":"A. Schrijver,\n                      Combinatorial Optimization: Polyhedra and Efficiency\n                      , Springer, Berlin, 2003."},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539790186704"},{"key":"atypb37","doi-asserted-by":"crossref","unstructured":"L. Seguin-Charbonneau and F. B. Shepherd,\n                      Maximum edge-disjoint paths in planar graphs with congestion 2\n                      , in Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), R. Ostrovsky, ed., 2011, pp. 200-209.","DOI":"10.1109\/FOCS.2011.30"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-42.1.178"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90228-2"},{"key":"atypb40","unstructured":"V. V. Vazirani,\n                      Approximation Algorithms\n                      , Springer, Berlin, 2001."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1319401","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:43:51Z","timestamp":1787319831000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1319401"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1319401"],"URL":"https:\/\/doi.org\/10.1137\/20m1319401","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}