Constant congestion routing of symmetric demands in planar directed graphs

Chandra Chekuri, E. N.E. Alina, Marcin Pilipczuk

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)2134-2160
Number of pages27
JournalSIAM Journal on Discrete Mathematics
Volume32
Issue number3
DOIs
StatePublished - 2018

Keywords

  • Directed treewidth
  • Disjoint paths
  • Planar digraphs
  • Routing

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Constant congestion routing of symmetric demands in planar directed graphs'. Together they form a unique fingerprint.

Cite this