## 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 = \{ s_{1}t_{1}, . . ., s_{k}t_{k}\} . The goal is to maximize the number of pairs that are routed along disjoint paths. A pair s_{i}t_{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)).

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