Randomly removing g handles at once

ABSTRACT

It was shown in [Indyk-Sidiropoulos 07] that any orientable graph of genus g can be probabilistically embedded into a graph of genus g-1 with constant distortion. Removing handles one by one gives an embedding into a distribution over planar graphs with distortion 2^O(g). By removing all $g$ handles at once, we present a probabilistic embedding with distortion O(g²) for both orientable and non-orientable graphs. Our result is obtained by showing that the minimum-cut graph of [Erickson-HarPeled 04] has low dilation, and then randomly cutting this graph out of the surface using the Peeling Lemma from [Lee-Sidiropoulos 08].

REFERENCES

• 1: 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]
• 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: Glencora Borradaile , Philip Klein, Exploiting planarity for network flow and connectivity problems, Brown University, Providence, RI, 2008
• 4: G. Borradaile, E. Demaine, and S. Tazari. Polynomial-time approximation schemes for subset-connectivity problems in bounded genus graphs. In Proceedings of STACS, 2009.
• 5: D. E. Carroll and A. Goel. Lower bounds for embedding into distributions over excluded minor graph families. In ESA, pages 146--156, 2004.
• 6: J. Erickson and S. Har-Peled. Optimally cutting a surface into a disk. Discrete & Computational Geometry, 31(1):37--59, 2004.
• 7: 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]
• 8: 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.
• 9: 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
• 10: 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
• 11: 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]
• 12: 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]
• 13: James R. Lee , Anastasios Sidiropoulos, On the geometry of graphs with a forbidden minor, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA [doi>10.1145/1536414.1536450]
• 14: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 15: B. Mohar and C. Thomassen. Graphs on Surfaces. John Hopkins, 2001.
• 16: 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]

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