@article{bb78f7690758417b8526ae4cc7bcb74d,

title = "Constant congestion routing of symmetric demands in planar directed graphs",

abstract = "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 \scrM = \{ s1t1, . . ., sktk\} . The goal is to maximize the number of pairs that are routed along disjoint paths. A pair siti is routed in the symmetric setting if there is a directed path connecting si to ti and a directed path connecting ti to si. 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/polylog(h)).",

keywords = "Directed treewidth, Disjoint paths, Planar digraphs, Routing",

author = "Chandra Chekuri and Alina, {E. N.E.} and Marcin Pilipczuk",

note = "Funding Information: \ast Received by the editors October 5, 2017; accepted for publication (in revised form) May 14, 2018; published electronically August 21, 2018. An extended abstract of this work has been presented at ICALP 2016 [8]. http://www.siam.org/journals/sidma/32-3/M115069.html Funding: The first author's work was partially supported by NSF grant CCF-1319376. The third author's work was partially supported by DIMAP and by Warwick-QMUL Alliance in Advances in Discrete Mathematics and its Applications. \dagger Department of Computer Science, University of Illinois, Urbana-Champaign, Urbana, IL 61801 (chekuri@illinois.edu). \ddagger Department of Computer Science, Boston University, Boston, MA 02215 (aene@bu.edu). \S Institute of Informatics, University of Warsaw, Warsaw, 02-097, Poland (malcin@mimuw.edu.pl). Funding Information: The first author's work was partially supported by NSF grant CCF-1319376. The third author's work was partially supported by DIMAP and by Warwick-QMUL Alliance in Advances in Discrete Mathematics and its Applications. Publisher Copyright: {\textcopyright} 2018 Society for Industrial and Applied Mathematics.",

year = "2018",

doi = "10.1137/17M1150694",

language = "English (US)",

volume = "32",

pages = "2134--2160",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}