Constant congestion routing of symmetric demands in planar directed graphs

Chandra Chekuri, Alina Ene, Marcin Pilipczuk

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 M = {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 poly-logarithmic 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 constant congestion crossbar of size (h/polylog(h)).

Original languageEnglish (US)
Title of host publication43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
EditorsYuval Rabani, Ioannis Chatzigiannakis, Davide Sangiorgi, Michael Mitzenmacher
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770132
DOIs
StatePublished - Aug 1 2016
Event43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 - Rome, Italy
Duration: Jul 12 2016Jul 15 2016

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume55
ISSN (Print)1868-8969

Other

Other43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
CountryItaly
CityRome
Period7/12/167/15/16

    Fingerprint

Keywords

  • Disjoint paths
  • Planar directed graph
  • Symmetric demands

ASJC Scopus subject areas

  • Software

Cite this

Chekuri, C., Ene, A., & Pilipczuk, M. (2016). Constant congestion routing of symmetric demands in planar directed graphs. In Y. Rabani, I. Chatzigiannakis, D. Sangiorgi, & M. Mitzenmacher (Eds.), 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 [7] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 55). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ICALP.2016.7