{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T09:14:07Z","timestamp":1787390047810,"version":"build-2736575974"},"reference-count":30,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>We study the maximum edge-disjoint paths problem in undirected planar graphs: given a graph G and node pairs (demands) $s_1t_1$, $s_2t_2$, $\\dots$, $s_kt_k$, the goal is to maximize the number of demands that can be connected (routed) by edge-disjoint paths. The natural multicommodity flow relaxation has an $\\Omega(\\sqrt{n})$ integrality gap, where n is the number of nodes in G. Motivated by this, we consider solutions with small constant congestion $c&gt;1$, that is, solutions in which up to c paths are allowed to use an edge (alternatively, each edge has a capacity of c). In previous work we obtained an $O(\\log n)$ approximation with congestion 2 via the flow relaxation. This was based on a method of decomposing into well-linked subproblems. In this paper we obtain an $O(1)$ approximation with congestion 4. To obtain this improvement we develop an alternative decomposition that is specific to planar graphs. The decomposition produces instances that we call Okamura\u2013Seymour (OS) instances. These have the property that all terminals lie on a single face. Another ingredient we develop is a constant factor approximation for the all-or-nothing flow problem on OS instances via the flow relaxation.<\/jats:p>","DOI":"10.1137\/060674442","type":"journal-article","created":{"date-parts":[[2009,5,29]],"date-time":"2009-05-29T12:34:17Z","timestamp":1243600457000},"page":"281-301","source":"Crossref","is-referenced-by-count":23,"title":["Edge-Disjoint Paths in Planar Graphs with Constant Congestion"],"prefix":"10.1137","volume":"39","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"F. Bruce","family":"Shepherd","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2009,5,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1145\/1183907.1183910"},{"key":"R2","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, 2005, pp. 226\u2013244.","DOI":"10.1109\/SFCS.2005.41"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794285983"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/1273340.1273343"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"C. Chekuri, S. Khanna, and F. B. Shepherd,\n                      The all-or-nothing multicommodity flow problem\n                      , in Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 156\u2013165.","DOI":"10.1145\/1007352.1007383"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"C. Chekuri, S. Khanna, and F. B. Shepherd,\n                      Edge-disjoint paths in planar graphs\n                      , in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2004, pp. 71\u201380.","DOI":"10.1109\/FOCS.2004.27"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"C. Chekuri, S. Khanna, and F. B. Shepherd,\n                      Multicommodity flow, well-linked terminals, and routing problems\n                      , in Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005, pp. 183\u2013192.","DOI":"10.1145\/1060590.1060618"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a007"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"C. Chekuri, S. Khanna, and F. B. Shepherd,\n                      Edge-disjoint paths in planar graphs with constant congestion\n                      , in Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006, pp. 757\u2013766.","DOI":"10.1145\/1132516.1132621"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/0205048"},{"key":"R11","unstructured":"L. R. Ford and D. R. Fulkerson,\n                      Flows in Networks\n                      , Princeton University Press, Princeton, NJ, 1962."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90046-2"},{"key":"R13","unstructured":"A. Frank,\n                      Packing paths, cuts, and circuits\u2014a survey\n                      , in Paths, Flows and VLSI-Layout, B. Korte, L. Lov\u00e1sz, H. J. Pr\u00f6mel, and A. Schrijver, eds., Springer-Verlag, Berlin, 1990, pp. 49\u2013100."},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523685"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"R. M. Karp,\n                      Reducibility among combinatorial problems\n                      , in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds., Plenum Press, New York, 1972, pp. 85\u2013103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"P. Klein, S. Plotkin, and S. Rao,\n                      Planar graphs, multicommodity flow, and network decomposition\n                      , in Proceedings of the 25th Annual ACM Symposium on Theory of Computing, 1993, pp. 682\u2013690.","DOI":"10.1145\/167088.167261"},{"key":"R17","unstructured":"J. M. Kleinberg,\n                      Approximation Algorithms for Disjoint Paths Problems\n                      , Ph.D. thesis, MIT, Cambridge, MA, 1996."},{"key":"R18","doi-asserted-by":"crossref","unstructured":"J. M. Kleinberg,\n                      An approximation algorithm for the disjoint paths problem in even-degree planar graphs\n                      , in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005, pp. 627\u2013636.","DOI":"10.1109\/SFCS.2005.18"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1579"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"J. M. Kleinberg and \u00c9.  Tardos,\n                      Disjoint paths in densely embedded graphs\n                      , in Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, 1995, pp. 52\u201361.","DOI":"10.1109\/SFCS.1995.492462"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"S. G. Kolliopoulos,\n                      Edge disjoint paths and unsplittable flow\n                      , in Handbook on Approximation Algorithms and Metaheuristics, Chapman & Hall\/CRC Press, Boca Raton, FL, 2007.","DOI":"10.1201\/9781420010749.ch57"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200757"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.4064\/fm-10-1-96-115"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(81)80012-3"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"H. R\u00e4cke,\n                      Minimizing congestion in general networks\n                      , in Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002, pp. 43\u201352.","DOI":"10.1109\/SFCS.2002.1181881"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"S. Rao,\n                      Small distortion and volume preserving embeddings for planar and Euclidean metrics\n                      , in Proceedings of the 15th Annual ACM Symposium on Computational Geometry, 1999, pp. 300\u2013306.","DOI":"10.1145\/304893.304983"},{"key":"R28","unstructured":"N. Robertson and P. D. Seymour,\n                      Outline of a disjoint paths algorithm\n                      , in Paths, Flows and VLSI-Layout, B. Korte, L. Lov\u00e1sz, H. J. Pr\u00f6mel, and A. Schrijver, eds., Springer-Verlag, Berlin, 1990, pp. 267\u2013292."},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1073"},{"key":"R30","unstructured":"A. Schrijver,\n                      Combinatorial Optimization: Polyhedra and Efficiency\n                      , Springer-Verlag, Berlin, 2003."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/060674442","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:19:53Z","timestamp":1787336393000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/060674442"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1137\/060674442"],"URL":"https:\/\/doi.org\/10.1137\/060674442","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]}}}