Probabilistic embeddings of bounded genus graphs into planar graphs

ABSTRACT

A probabilistic C-embedding of a (guest) metric M into a collection of(host) metrics M'₁, ..., M'_k is a randomized mapping F of M intoone of the M'₁, ..., M'_k such that, for any two points p,q in theguest metric: The distance between F(p) and F(q) in any M'_i is not smaller thanthe original distance between p and q. The expected distance between F(p) and F(q) in (random) M'_i is notgreater than some constant C times the original distance, for C≥ 1. The constant C is called the distortion of the embedding. Low-distortion probabilistic embeddings enable reducing algorithmicproblems over "hard" guest metrics into "easy" host metrics.We show that every metric induced by a graph of bounded genus can beprobabilistically embedded into planar graphs, with constant distortion. The embedding can be computed efficiently, given a drawing of the graphon a genus-g surface.

REFERENCES

• 1: [1] M. O. Albertson and J. P. Hutchinson. On the independence ratio of a graph. J. Graph Theory, 2:1-8, 1978.
• 2: Noga Alon , Richard M. Karp , David Peleg , Douglas West, A Graph-Theoretic Game and its Application to the $k$-Server Problem, SIAM Journal on Computing, v.24 n.1, p.78-100, Feb. 1995 [doi>10.1137/S0097539792224474]
• 3: Brenda S. Baker, Approximation algorithms for NP-complete problems on planar graphs, Journal of the ACM (JACM), v.41 n.1, p.153-180, Jan. 1994 [doi>10.1145/174644.174650]
• 4: 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
• 5: 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]
• 6: [6] S. Cabello and E. Chambers. Multiple source shortest paths in a genus g graph. In SODA, 2007.
• 7: [7] D. E. Carroll and A. Goel. Lower bounds for embedding into distributions over excluded minor graph families. In ESA, pages 146-156, 2004.
• 8: Chandra Chekuri , Anupam Gupta , Ilan Newman , Yuri Rabinovich , Alistair Sinclair, Embedding k-outerplanar graphs into ℓ1, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 9: Michael Elkin , Yuval Emek , Daniel A. Spielman , Shang-Hua Teng, Lower-stretch spanning trees, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060665]
• 10: Yuval Emek , David Peleg, A tight upper bound on the probabilistic embedding of series-parallel graphs, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1045-1053, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109673]
• 11: [11] P. Erdös and H. Sachs. Reguläre graphen gegebener taillenweite mit minimaler knotenzahl. Wiss. Z. Matin-Luther-Univ. Halle-Wittenberg Math. -Natur. Reihe, 12:251-257, 1963.
• 12: 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]
• 13: Anupam Gupta, Steiner points in tree metrics don't (really) help, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.220-227, January 07-09, 2001, Washington, D.C., United States
• 14: Anupam Gupta , Alistair Sinclair , Ilan Newman , Yuri Rabinovich, Cuts, Trees and -Embeddings of Graphs, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.399, October 17-18, 1999
• 15: 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
• 16: [16] R. M. Karp. A 2k-competitive algorithm for the circle. Manuscript, 1989.
• 17: [17] R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor. Measured descent: A new embedding method for finite metrics. Geom. Funct. Anal., 2004. To appear.
• 18: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 19: [19] B. Mohar and C. Thomassen. Graphs on Surfaces. John Hopkins, 2001.
• 20: [20] Y. Rabinovich and R. Raz. Lower bounds on the distortion of embedding finite metric spaces in graphs. Discrete Computational Geometry, 1998.
• 21: Kunal Talwar, Bypassing the embedding: algorithms for low dimensional metrics, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007399]
• 22: [22] D. Thilikos. Personal Communication.
• 23: C. Thomassen, Embeddings of graphs with no short noncontractible cycles, Journal of Combinatorial Theory Series B, v.48 n.2, p.155-177, Apr. 1990 [doi>10.1016/0095-8956(90)90115-G]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Theory

Keywords:
bounded genus graphs, embeddings, planar graphs, probabilistic approximation