{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:43:05Z","timestamp":1787323385465,"version":"build-2736575974"},"reference-count":43,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100015065","name":"DIMAP","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100015065","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Warwick-QMUL"},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1319376"],"award-info":[{"award-number":["CCF-1319376"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We study the problem of routing symmetric demand pairs in planar digraphs. The input consists of a directed planar graph $G=(V,E)$ and a collection of $k$ source-destination pairs $\\mathcal{M} = \\{s_1t_1, \\dots, s_kt_k\\}$. The goal is to maximize the number of pairs that are routed along disjoint paths. A pair $s_it_i$ is routed in the symmetric setting if there is a directed path connecting $s_i$ to $t_i$ and a directed path connecting $t_i$ to $s_i$. In this paper we obtain a randomized polylogarithmic approximation with constant congestion for this problem in planar digraphs. The main technical contribution is to show that a planar digraph with directed treewidth $h$ contains a relaxed cylindrical grid (which can serve as a constant congestion crossbar in the context of a routing algorithm) of size $\\Omega(h\/\\mathrm{polylog}(h))$.<\/jats:p>","DOI":"10.1137\/17m1150694","type":"journal-article","created":{"date-parts":[[2018,8,21]],"date-time":"2018-08-21T14:30:50Z","timestamp":1534861850000},"page":"2134-2160","source":"Crossref","is-referenced-by-count":3,"title":["Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs"],"prefix":"10.1137","volume":"32","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alina","family":"Ene","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,8,21]]},"reference":[{"key":"atypb1","first-page":"277","author":"Andrews M.","year":"2010","journal-title":"Proceedings of IEEE FOCS"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-010-2455-9"},{"key":"atypb3","first-page":"291","author":"Chekuri C.","year":"2013","journal-title":"Procedings of ACM STOC"},{"key":"atypb4","first-page":"242","author":"Chekuri C.","year":"2015","journal-title":"Proceedings of ACM-SIAM SODA"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1145\/2820609"},{"key":"atypb6","first-page":"326","author":"Chekuri C.","year":"2013","journal-title":"Proceedings of ACM-SIAM SODA"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0856-z"},{"key":"atypb8","unstructured":"C. Chekuri, A. Ene, and M. Pilipczuk,\n                      Constant congestion routing of symmetric demands in planar directed graphs\n                      , in Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016, Rome, Italy, I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani, and D. Sangiorgi, eds., pp. 7:1-7:14; also available online fromhttps:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.7."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/130906830"},{"key":"atypb10","first-page":"183","author":"Chekuri C.","year":"2005","journal-title":"Procedings of ACM STOC"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a007"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/100796820"},{"key":"atypb13","first-page":"55","author":"Chen J.","year":"2008","journal-title":"J. ACM"},{"key":"atypb14","first-page":"645","author":"Chuzhoy J.","year":"2015","journal-title":"Proceedings of ACM STOC"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/130910464"},{"key":"atypb16","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1145\/1250790.1250816","author":"Chuzhoy J.","year":"2007","journal-title":"Proceedings of ACM STOC"},{"key":"atypb17","first-page":"86","author":"Chuzhoy J.","year":"2017","journal-title":"Proceedings of ACM STOC"},{"key":"atypb18","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 SIGACT Symposium on Theory of Computing, Cambridge, MA, 2016, D. Wichs and Y. Mans, eds., pp. 556-569,https:\/\/doi.org\/10.1145\/2897518.2897538.","DOI":"10.1145\/2897518.2897538"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1145\/2893472"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"M. Cygan, F. Fomin, L. Kowalik, D. Loksthanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Parameterized Algorithms\n                      , Springer, New York, 2015.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2140-4"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-035-8"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1145\/347476.347478"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90009-2"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.2031"},{"key":"atypb26","unstructured":"T. Johnson, N. Robertson, P. D. Seymour, and R. Thomas,\n                      Excluding a Grid Minor in Digraphs\n                      , manuscript,http:\/\/arxiv.org\/abs\/1510.00473, 2001."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2335205"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2347277"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1002\/net.1975.5.1.45"},{"key":"atypb30","first-page":"72","author":"Kawarabayashi K.","year":"2014","journal-title":"Proceedings of ACM-SIAM SODA"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"K. Kawarabayashi and S. Kreutzer,\n                      The directed grid theorem\n                      , in Proceedings of ACM STOC, 2015.","DOI":"10.1145\/2746539.2746586"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1145\/1538902.1538903"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0833"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0370-6"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"atypb36","unstructured":"A. Louis,\n                      Cut-Matching Games on Directed Graphs\n                      , CoRR, abs\/1010.1047, 2010."},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1137\/080715093"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0653(05)80061-7"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1007\/BF01271272"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1007\/BF01271273"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1073"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200760"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1150694","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:59:21Z","timestamp":1787320761000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1150694"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1150694"],"URL":"https:\/\/doi.org\/10.1137\/17m1150694","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}