Many distances in planar graphs

ABSTRACT

Let G be a planar graph with n vertices and non-negative edge-lengths. Given a set of k pairs of vertices, we are interested in computing the distance in G between those k pairs of vertices. We describe how this can be achieved in O(n^2/3k^2/3 log n + n^4/3log^1/3 n) time, improving previous results for a large range of k. As possible applications, we show how this result speeds up previous algorithms for finding shortest non-contractible cycles for graphs on a bounded-genus surface or for computing the dilation of a geometric planar graph.

REFERENCES

• 1: Srinivasa Rao Arikati , Danny Z. Chen , L. Paul Chew , Gautam Das , Michiel H. M. Smid , Christos D. Zaroliagis, Planar Spanners and Approximate Shortest Path Queries among Obstacles in the Plane, Proceedings of the Fourth Annual European Symposium on Algorithms, p.514-528, September 25-27, 1996
• 2: S. Cabello and B. Mohar. Finding shortest non-separating and non-contractible cycles for topologically embedded graphs. In ESA '05, volume 3669 of LNCS, pages 131--142. Springer, 2005.
• 3: T. Chan. All-pairs shortest paths with real weights in O(n3 / log n) time. In WADS'05, volume 3608 of LNCS, pages 318--324. Springer, 2005.
• 4: Danny Z. Chen , Jinhui Xu, Shortest path queries in planar graphs, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.469-478, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335359]
• 5: Hristo Djidjev, On-Line Algorithms for Shortest Path Problems on Planar Digraphs, Proceedings of the 22nd International Workshop on Graph-Theoretic Concepts in Computer Science, p.151-165, June 12-14, 1996
• 6: D. Eppstein. Spanning trees and spanners. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, chapter 9, pages 425--461. Elsevier, 2000.
• 7: J. Erickson and S. Har-Peled. Optimally cutting a surface into a disk. Discrete Comput. Geom., 31(1):37--59, 2004.
• 8: J. Fakcharoenphol, Planar Graphs, Negative Weight Edges, Shortest Paths, and Near Linear Time, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.232, October 14-17, 2001
• 9: Greg N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM Journal on Computing, v.16 n.6, p.1004-1022, December 1, 1987 [doi>10.1137/0216064]
• 10: Greg N. Frederickson, Planar graph decomposition and all pairs shortest paths, Journal of the ACM (JACM), v.38 n.1, p.162-204, Jan. 1991 [doi>10.1145/102782.102788]
• 11: J. Gudmundsson, C. Levcopoulos, G. Narasimhan, and M. Smid. Approximate distance oracles for geometric spanners. Technical Report TR-04-08, School of Computer Science, Carleton University, 2004.
• 12: A. Hatcher. Algebraic Topology. Cambridge University Press, 2001. Available at http://www.math.cornell. edu/~hatcher/.
• 13: Monika R. Henzinger , Philip Klein , Satish Rao , Sairam Subramanian, Faster shortest-path algorithms for planar graphs, Journal of Computer and System Sciences, v.55 n.1, p.3-23, Aug. 1997 [doi>10.1006/jcss.1997.1493]
• 14: Philip N. Klein, Multiple-source shortest paths in planar graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 15: Lukasz Kowalik , Maciej Kurowski, Short path queries in planar graphs in constant time, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780565]
• 16: R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM J. Appl. Math., 36:177--189, 1979.
• 17: Gary L Miller, Finding small simple cycle separators for 2-connected planar graphs, Journal of Computer and System Sciences, v.32 n.3, p.265-279, June 1986 [doi>10.1016/0022-0000(86)90030-9]
• 18: B. Mohar and C. Thomassen. Graphs on Surfaces. Johns Hopkins University Press, Baltimore, 2001.
• 19: Giri Narasimhan , Michiel Smid, Approximating the Stretch Factor of Euclidean Graphs, SIAM Journal on Computing, v.30 n.3, p.978-989, 2000 [doi>10.1137/S0097539799361671]
• 20: Mikkel Thorup, Compact oracles for reachability and approximate distances in planar digraphs, Journal of the ACM (JACM), v.51 n.6, p.993-1024, November 2004 [doi>10.1145/1039488.1039493]
• 21: Uri Zwick, Exact and Approximate Distances in Graphs - A Survey, Proceedings of the 9th Annual European Symposium on Algorithms, p.33-48, August 28-31, 2001

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory