Embedding k-outerplanar graphs into ℓ1

ABSTRACT

We show that the shortest-path metric of any k-outerplanar graph, for any fixed k, can be approximated by a probability distribution over tree metrics with constant distortion, and hence also embedded into l1 with constant distortion. These graphs play a central role in polynomial time approximation schemes for many NP-hard optimization problems on general planar graphs, and include the family of weighted k × n planar grids.This result implies a constant upper bound on the ratio between the sparsest cut and the maximum concurrent flow in multicommodity networks for k-outerplanar graphs, thus extending a classical theorem of Okamura and Seymour [26] for outerplanar graphs, and of Gupta et al. [17] for treewidth-2 graphs. In addition, we obtain improved approximation ratios for k-outerplanar graphs on various problems for which approximation algorithms are based on probabilistic tree embeddings. We also conjecture that our random tree embeddings for k-outerplanar graphs can serve as a building block for more powerful l1 embeddings in future.

REFERENCES

• 1: 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]
• 2: 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]
• 3: B. Awerbuch , Y. Azar, Buy-at-bulk network design, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.542, October 19-22, 1997
• 4: 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]
• 5: 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
• 6: 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]
• 7: Daniel Bienstock and Clyde L. Monma. On the complexity of embedding planar graphs to minimize certain distance measures. Algorithmica, 5(1):93--109, 1990.
• 8: Hans L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theoretical Computer Science, v.209 n.1-2, p.1-45, Dec. 6, 1998 [doi>10.1016/S0304-3975(97)00228-4 ]
• 9: Jean Bourgain. On Lipschitz embeddings of finite metric spaces in Hilbert space. Israel Journal of Mathematics, 52(1--2):46--52, 1985.
• 10: Moses Charikar , Chandra Chekuri , Ashish Goel , Sudipto Guha, Rounding via trees: deterministic approximation algorithms for group Steiner trees and k-median, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.114-123, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276719]
• 11: Moses Charikar , Chandra Chekuri , Ashish Goel , Sudipto Guha , Serge Plotkin, Approximating a Finite Metric by a Small Number of Tree Metrics, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.379, November 08-11, 1998
• 12: Michel Marie Deza and Monique Laurent. Geometry of Cuts and Metrics. Springer Verlag, 1997.
• 13: Reinhard Diestel. Graph Theory. Springer-Verlag, New York, 1997.
• 14: András Frank. Packing paths, circuits, and cuts-a survey. In Bernhard Korte, László Lovász, Hans Jürgen Prömel, and Alexander Schrijver, editors, Paths, Flows and VLSl-Layout, pages 47--100. Springer-Verlag, 1990.
• 15: Naveen Garg , Goran Konjevod , R. Ravi, A polylogarithmic approximation algorithm for the Steiner group tree problem, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.253-259, January 25-27, 1998, San Francisco, California, United States
• 16: 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
• 17: 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
• 18: R. Halin. Studies on minimally n-connected graphs. In D.J.A. Welsh, editor, Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), pages 129--136. Academic Press, London, 1971.
• 19: 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
• 20: Richard M. Karp. A 2k-competitive algorithm for the circle. Manuscript, 1989.
• 21: Sanjeev Khanna , Rajeev Motwani, Towards a syntactic characterization of PTAS, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.329-337, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237979]
• 22: Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215--245, 1995. (Preliminary version in: 35th Annual Symposium on Foundations of Computer Science, pages 577--591, 1994).
• 23: Jiří Matošek. Lectures in Discrete Geometry. Springer-Verlag, to appear.
• 24: Ilan Newman , Yuri Rabinovich, A lower bound on the distortion of embedding planar metrics into Euclidean space, Proceedings of the eighteenth annual symposium on Computational geometry, p.94-96, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513412]
• 25: Ilan Newman, Yuri Rabinovich, and Michael Saks. unpublished notes.
• 26: Haruko Okamura and Paul D. Seymour. Multicommodity flows in planar graphs. Journal of Combinatorial Theory Series B, 31(1):75--81, 1981.
• 27: 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]
• 28: Neil Robertson and Paul D. Seymour. Graph minors. III. Planar tree-width. J. Combin. Theory Ser. B, 36(1):49--64, 1984.
• 29: Alexander Schrijver. Homotopic routing methods. In Bernhard Korte, László Lovász, Hans Jürgen Prömel, and Alexander Schrijver, editors, Paths, Flows and VLSI-Layout, pages 329--371. Springer-Verlag, 1990.
• 30: Farhad Shahrokhi , D. W. Matula, The maximum concurrent flow problem, Journal of the ACM (JACM), v.37 n.2, p.318-334, April 1990 [doi>10.1145/77600.77620]
• 31: David B. Shmoys, Cut problems and their application to divide-and-conquer, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 32: Maciej M. Syslo and Andrzej Proskurowski. On Halin graphs. In Graph theory (Lagów, 1981), pages 248--256. Springer, Berlin, 1983.
• 33: Douglas B. West. Introduction to graph theory. Prentice Hall Inc., Upper Saddle River, NJ, 1996.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees
      G.2.m Miscellaneous

General Terms:
Algorithms, Theory