[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Many Distances in Planar Graphs

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We show how to compute in O(n 4/3log 1/3 n+n 2/3 k 2/3log n) time the distance between k given pairs of vertices of a planar graph G with n vertices. This improves previous results whenever (n/log n)5/6≤k≤n 2/log 6 n. As an application, we speed up previous algorithms for computing the dilation of geometric planar graphs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Arikati, S., Chen, D.Z., Chew, L.P., Das, G., Smid, M., Zaroliagis, C.: Planar spanners and approximate shortest path queries among obstacles in the plane. In: ESA’96. LNCS, vol. 1136, pp. 514–528. Springer, Berlin (1996)

    Google Scholar 

  2. Cabello, S.: Many distances in planar graphs. In: SODA ’06: Proc. 17th Symp. Discrete Algorithms, pp. 1213–1220. ACM Press, New York (2006)

    Chapter  Google Scholar 

  3. Cabello, S., Chambers, E.W.: Multiple source shortest paths in a genus g graph. In: SODA ’07: Proc. 18th Symp. Discrete Algorithms, pp. 89–97 (2007)

    Google Scholar 

  4. Chan, T.M.: All-pairs shortest paths with real weights in O(n 3/log n) time. Algorithmica 50(2), 236–243 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  5. Chen, D.Z., Xu, J.: Shortest path queries in planar graphs. In: STOC ’00: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, pp. 469–478 (2000)

    Chapter  Google Scholar 

  6. Djidjev, H.N.: Efficient algorithms for shortest path problems on planar digraphs. In: d’Amore, F., Franciosa, P.G., Marchetti-Spaccamela, A. (eds.) WG’96. LNCS, vol. 1197, pp. 151–165. Springer, Berlin (1997)

    Google Scholar 

  7. Eppstein, D.: Spanning trees and spanners. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 425–461. Elsevier, Amsterdam (2000). Chap. 9

    Chapter  Google Scholar 

  8. Fakcharoenphol, J., Rao, S.: Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci. 72(5), 868–889 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  9. Frederickson, G.N.: Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput. 16, 1004–1022 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  10. Frederickson, G.N.: Planar graph decomposition and all pairs shortest paths. J. ACM 38(1), 162–204 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  11. Goodrich, M.T.: Planar separators and parallel polygon triangulation. J. Comput. Syst. Sci. 51(3), 374–389 (1995)

    Article  MathSciNet  Google Scholar 

  12. Gudmundsson, J., Levcopoulos, C., Narasimhan, G., Smid, M.: Approximate distance oracles for geometric spanners. ACM Trans. Algorithms 4(1), 1–34 (2008)

    Article  MathSciNet  Google Scholar 

  13. Henzinger, M.R., Klein, P.N., Rao, S., Subramanian, S.: Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci. 55(1), 3–23 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  14. Klein, P., Mozes, S., Weimann, O.: Shortest paths in directed planar graphs with negative lengths: A linear-space O(nlog 2 n)-time algorithm. ACM Trans. Algorithms 6(2), 1–18 (2010)

    Article  MathSciNet  Google Scholar 

  15. Klein, P.N.: Multiple-source shortest paths in planar graphs. In: SODA ’05: Proc. 16th Symp. Discrete Algorithms, pp. 146–155 (2005)

    Google Scholar 

  16. Kowalik, L., Kurowski, M.: Short path queries in planar graphs in constant time. In: STOC ’03: Proc. 35th Symp. Theory of Computing, pp. 143–148 (2003)

    Chapter  Google Scholar 

  17. Kutz, M.: Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time. In: SOCG ’06: Proc. 22nd Symp. Comput. Geom., pp. 430–438 (2006)

    Google Scholar 

  18. Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36, 177–189 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  19. Lipton, R.J., Rose, D., Tarjan, R.E.: Generalized nested dissection. SIAM J. Numer. Anal. 16, 346–358 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  20. Miller, G.L.: Finding small simple cycle separators for 2-connected planar graphs. J. Comput. Syst. Sci. 32, 265–279 (1986)

    Article  MATH  Google Scholar 

  21. Narasimhan, G., Smid, M.: Approximating the stretch factor of Euclidean graphs. SIAM J. Comput. 30, 978–989 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  22. Overmars, M.H.: The Design of Dynamic Data Structures. Lecture Notes in Computer Science, vol. 156. Springer, Berlin (1983)

    MATH  Google Scholar 

  23. Tazari, S., Müller-Hannemann, M.: Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation. Discrete Appl. Math. 157, 673–684 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  24. Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM 51(6), 993–1024 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  25. Zwick, U.: Exact and approximate distances in graphs—A survey. In: ESA 2001. LNCS, vol. 2161, pp. 33–48. Springer, Berlin (2001)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Faculty of Mathematics and Physics, University of Ljubljana, Ljubljana, Slovenia

    Sergio Cabello

  2. Department of Mathematics, Institute for Mathematics, Physics and Mechanics, Ljubljana, Slovenia

    Sergio Cabello

Authors
  1. Sergio Cabello
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sergio Cabello.

Additional information

A preliminary version was presented at the 17th Annual ACM-SIAM Symposium on Discrete algorithms [2]. Research partially supported by the European Community Sixth Framework Programme under a Marie Curie Intra-European Fellowship and by the Slovenian Research Agency, project J1-7218 and program P1-0297.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Cabello, S. Many Distances in Planar Graphs. Algorithmica 62, 361–381 (2012). https://doi.org/10.1007/s00453-010-9459-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-010-9459-0

Keywords

Search

Navigation