LIPIcs.ISAAC.2020.41.pdf
- Filesize: 0.73 MB
- 11 pages
Document
Multicommodity Flows in Planar Graphs with Demands on Faces
Author
-
Part of:
Volume:
31st International Symposium on Algorithms and Computation (ISAAC 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-12-04
File
Document Identifiers
Acknowledgements
The author would like to thank Naveen Garg for useful discussions.
Cite As Get 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)
0PDF Downloads
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.