@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",
}