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)).
Original language | English (US) |
---|---|
Pages (from-to) | 2134-2160 |
Number of pages | 27 |
Journal | SIAM Journal on Discrete Mathematics |
Volume | 32 |
Issue number | 3 |
DOIs | |
State | Published - 2018 |
Keywords
- Directed treewidth
- Disjoint paths
- Planar digraphs
- Routing
ASJC Scopus subject areas
- General Mathematics