Constant congestion routing of symmetric demands in planar directed graphs

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 = \{ s₁t₁, . . ., 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 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)).