Multicommodity Flows in Planar Graphs with Demands on Faces

Kumar, Nikhil

doi:10.4230/LIPIcs.ISAAC.2020.41

File

LIPIcs.ISAAC.2020.41.pdf

Filesize: 0.73 MB
11 pages

Document Identifiers

DOI: 10.4230/LIPIcs.ISAAC.2020.41
URN: urn:nbn:de:0030-drops-133857

Author Details

Nikhil Kumar

Indian Institute of Technology Delhi, India

Acknowledgements

The author would like to thank Naveen Garg for useful discussions.

Cite AsGet BibTex

Nikhil Kumar. Multicommodity Flows in Planar Graphs with Demands on Faces. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 41:1-41:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ISAAC.2020.41

Abstract

We consider the problem of multicommodity flows in planar graphs. Seymour [Seymour, 1981] showed that if the union of supply and demand graphs is planar, then the cut condition is also sufficient for routing demands. Okamura-Seymour [Okamura and Seymour, 1981] showed that if the supply graph is planar and all demands are incident on one face, then again the cut condition is sufficient for routing demands. We consider a common generalization of these settings where the end points of each demand are on the same face of the planar graph. We show that if the source sink pairs on each face of the graph are such that sources and sinks appear contiguously on the cycle bounding the face, then the flow cut gap is at most 3. We come up with a notion of approximating demands on a face by convex combination of laminar demands to prove this result.

Subject Classification

ACM Subject Classification

Theory of computation → Routing and network design problems

Keywords

Combinatorial Optimization
Multicommodity Flow
Network Design

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

Richard Bellman. On a routing problem. Quarterly of applied mathematics, 16(1):87-90, 1958.
Amit Chakrabarti, Alexander Jaffe, James R Lee, and Justin Vincent. Embeddings of topological graphs: Lossy invariants, linearization, and 2-sums. In Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on, pages 761-770. IEEE, 2008.
Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, and Alistair Sinclair. Embedding k-outerplanar graphs into l1. SIAM Journal on Discrete Mathematics, 20(1):119-136, 2006.
Chandra Chekuri, F Bruce Shepherd, and Christophe Weibel. Flow-cut gaps for integer and fractional multiflows. Journal of Combinatorial Theory, Series B, 103(2):248-273, 2013.
Arnold Filtser. A face cover perspective to 𝓁1 embeddings of planar graphs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1945-1954. SIAM, 2020.
Anupam Gupta, Ilan Newman, Yuri Rabinovich, and Alistair Sinclair. Cuts, trees and 𝓁1-embeddings of graphs. Combinatorica, 24(2):233-269, 2004.
Robert Krauthgamer, James R Lee, and Havana Rika. Flow-cut gaps and face covers in planar graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 525-534. SIAM, 2019.
Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215-245, June 1995.
Guyslain Naves and Christophe Weibel. Congestion in planar graphs with demands on faces. arXiv preprint, 2010. URL: http://arxiv.org/abs/1008.3653.
Haruko Okamura and Paul D Seymour. Multicommodity flows in planar graphs. Journal of Combinatorial Theory, Series B, 31(1):75-81, 1981.
Satish Rao. Small distortion and volume preserving embeddings for planar and euclidean metrics. In Proceedings of the fifteenth annual symposium on Computational geometry, pages 300-306. ACM, 1999.
Paul D Seymour. On odd cuts and plane multicommodity flows. Proceedings of the London Mathematical Society, 3(1):178-192, 1981.