On the geometry of graphs with a forbidden minor

ABSTRACT

We study the topological simplification of graphs via random embeddings, leading ultimately to a reduction of the Gupta-Newman-Rabinovich-Sinclair (GNRS) L₁ embedding conjecture to a pair of manifestly simpler conjectures. The GNRS conjecture characterizes all graphs that have an O(1)-approximate multi-commodity max-flow/min-cut theorem. In particular, its resolution would imply a constant factor approximation for the general Sparsest Cut problem in every family of graphs which forbids some minor. In the course of our study, we prove a number of results of independent interest.

REFERENCES

• 1: Yonatan Aumann , Yuval Rabani, An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm, SIAM Journal on Computing, v.27 n.1, p.291-301, Feb. 1998 [doi>10.1137/S0097539794285983]
• 2: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 3: Yair Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.161-168, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276725]
• 4: D. Carroll and A. Goel. Lower bounds for embedding into distributions over excluded minor graph families. In Proceedings of the 12th European Symposium on Algorithms, 2004.
• 5: Amit Chakrabarti , Alexander Jaffe , James R. Lee , Justin Vincent, Embeddings of Topological Graphs: Lossy Invariants, Linearization, and 2-Sums, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.761-770, October 25-28, 2008 [doi>10.1109/FOCS.2008.79]
• 6: Chandra Chekuri , Anupam Gupta , Ilan Newman , Yuri Rabinovich , Alistair Sinclair, Embedding k-Outerplanar Graphs into l₁, SIAM Journal on Discrete Mathematics, v.20 n.1, p.119-136, 2006 [doi>10.1137/S0895480102417379]
• 7: M. M. Deza and M. Laurent. Geometry of cuts and metrics, volume 15 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 1997.
• 8: R. Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer-Verlag, Berlin, third edition, 2005.
• 9: Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780608]
• 10: J. Fakcharoenphol and K. Talwar. An improved decomposition theorem for graphs excluding a fixed minor. In Proceedings of 6th Workshop on Approximation, Randomization, and Combinatorial Optimization, volume 2764 of Lecture Notes in Computer Science, pages 36--46. Springer, 2003.
• 11: Anupam Gupta , Ilan Newman , Yuri Rabinovich , Alistair Sinclair, Cuts, Trees and ℓ₁-Embeddings of Graphs*, Combinatorica, v.24 n.2, p.233-269, April 2004 [doi>10.1007/s00493-004-0015-x]
• 12: P. Indyk, Algorithmic Applications of Low-Distortion Geometric Embeddings, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.10, October 14-17, 2001
• 13: Piotr Indyk , Anastasios Sidiropoulos, Probabilistic embeddings of bounded genus graphs into planar graphs, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea [doi>10.1145/1247069.1247107]
• 14: Philip Klein , Serge A. Plotkin , Satish Rao, Excluded minors, network decomposition, and multicommodity flow, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.682-690, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167261]
• 15: J. R. Lee and A. Naor. Extending Lipschitz functions via random metric partitions. Invent. Math., 160(1):59--95, 2005.
• 16: J. R. Lee and P. Rhagevendra. Coarse differentiation and multi-flows in planar graphs. 2007.
• 17: Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
• 18: N. Linial. Finite metric-spaces-combinatorics, geometry and algorithms. In Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002), pages 573--586, Beijing, 2002. Higher Ed. Press.
• 19: N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215--245, 1995.
• 20: L. Lovász. Graph minor theory. Bull. Amer. Math. Soc. (N.S.), 43(1):75--86 (electronic), 2006.
• 21: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 22: H. Okamura and P. D. Seymour. Multicommodity flows in planar graphs. J. Combin. Theory Ser. B, 31(1):75--81, 1981.
• 23: Y. Rabinovich and R. Raz. Lower bounds on the distortion of embedding finite metric spaces in graphs. Discrete Comput. Geom., 19(1):79--94, 1998.
• 24: Satish Rao, Small distortion and volume preserving embeddings for planar and Euclidean metrics, Proceedings of the fifteenth annual symposium on Computational geometry, p.300-306, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304983]
• 25: Neil Robertson , P. D. Seymour, Graph minors, Journal of Combinatorial Theory Series B, v.77 n.1, p.162-210, Sept. 1999 [doi>10.1006/jctb.1999.1919]
• 26: N. Robertson and P. D. Seymour. Graph minors. I. Excluding a forest. J. Combin. Theory Ser. B, 35(1):39--61, 1983.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Algorithms, Theory

Keywords:
embeddings, forbidden minors, geometry of graphs