Coarse differentiation and multi-flows in planar graphs

2008/04/09 by James R. Lee, Lee, James R., Prasad Raghavendra +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory #Metric Geometry (math.MG) #math.CO #math.MG

paper · pdf · doi:10.48550/arxiv.0804.1573

15 pages, 2 figures; added additional bibliographic information

openalex publication_date 2008/04/09 · arxiv created 2009/10/01 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that the multi-commodity max-flow/min-cut gap for series-parallel graphs can be as bad as 2, matching a recent upper bound Chakrabarti, Jaffe, Lee, and Vincent for this class, and resolving one side of a conjecture of Gupta, Newman, Rabinovich, and Sinclair. This also improves the largest known gap for planar graphs from 3/2 to 2, yielding the first lower bound that doesn't follow from elementary calculations. Our approach uses the \em coarse differentiation method of Eskin, Fisher, and Whyte in order to lower bound the distortion for embedding a particular family of shortest-path metrics into L₁.

Cited by

• Improved Lower Bounds on Multiflow-Multicut Gaps

Related

• On constant multi-commodity flow-cut gaps for directed minor-free graphs
• Improved Lower Bounds on Multiflow-Multicut Gaps
• An Approximate Generalization of the Okamura-Seymour Theorem
• Flow-Cut Gaps and Face Covers in Planar Graphs
• Embeddings of Planar Quasimetrics into Directed ℓ₁ and Polylogarithmic Approximation for Directed Sparsest-Cut