Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Efficient Vertex-Label Distance Oracles for Planar Graphs

  • Published:
Theory of Computing Systems Aims and scope Submit manuscript

Abstract

We consider distance queries in vertex-labeled planar graphs. For any fixed 0 < 𝜖 ≤ 1/2 we show how to preprocess a directed planar graph with vertex labels and arc lengths into a data structure that answers queries of the following form. Given a vertex u and a label λ return a (1 + 𝜖)-approximation of the distance from u to its closest vertex with label λ. For a directed planar graph with n vertices, such that the ratio of the largest to smallest arc length is bounded by N, the preprocessing time is O(𝜖 − 2 n lg 3n lg(n N)), the data structure size is O(𝜖 − 1 n lg n lg(n N)), and the query time is O(lg lg n lg lg(n N) + 𝜖 − 1). We also point out that a vertex label distance oracle for undirected planar graphs suggested in an earlier version of this paper is incorrect.

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
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Notes

  1. The definitions in the literature differ in the choice of constant (3/4 in our case) as well as in the quantity according to which the balance of the separation is defined (number of faces in our case).

  2. 2SinceG r is planar, one may use [10] instead to achieveO(𝜖 − 1|E(G r )| lg |V (G)|)complexity. However this is not the bottleneck.

References

  1. Abraham, I., Chechik, S., Krauthgamer, R., Wieder, U.: Approximate nearest neighbor search in metrics of planar graphs. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pp. 20–42 (2015). https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.20

  2. Baswana, S., Gaur, A., Sen, S., Upadhyay, J.: Distance oracles for unweighted graphs: Breaking the quadratic barrier with constant additive error. In: Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), pp. 609–621 (2008). https://doi.org/10.1007/978-3-540-70575-8_50

  3. Baswana, S., Kavitha, T.: Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In: Proceedings of the 47th Annual Symposium on Foundations of Computer Science (FOCS), pp. 591–602 (2006). https://doi.org/10.1109/FOCS.2006.29

  4. Baswana, S., Sen, S.: Approximate distance oracles for unweighted graphs in expected O(n 2) time. ACM Trans. Algor. 2(4), 557–577 (2006). https://doi.org/10.1145/1198513.1198518

    Article  MATH  Google Scholar 

  5. Chechik, S.: Improved distance oracles and spanners for vertex-labeled graphs. In: Proceedings of the 20th European Symposium on Algorithms (ESA), pp. 325–336 (2012). https://doi.org/10.1007/978-3-642-33090-2_29 https://doi.org/10.1007/978-3-642-33090-2_29

  6. Chechik, S.: Approximate distance oracles with improved bounds. In: Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC), pp. 1–10 (2015)

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

    Article  MathSciNet  MATH  Google Scholar 

  8. Hagerup, T., Miltersen, P. B., Pagh, R.: Deterministic dictionaries. J. Algor. 41(1), 69–85 (2001). https://doi.org/10.1006/jagm.2001.1171

    Article  MathSciNet  MATH  Google Scholar 

  9. Harel, D., Tarjan, R. E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13(2), 338–355 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  10. 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  MathSciNet  MATH  Google Scholar 

  11. Hermelin, D., Levy, A., Weimann, O., Yuster, R.: Distance oracles for vertex-labeled graphs. In: Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP), pp. 490–501 (2011)

  12. Kawarabayashi, K., Klein, P. N., Sommer, C.: Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs. In: Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP), pp. 135–146 (2011)

  13. Kawarabayashi, K., Sommer, C., Thorup, M.: More compact oracles for approximate distances in undirected planar graphs. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 550–563 (2013)

  14. Klein, P. N.: Preprocessing an undirected planar network to enable fast approximate distance queries. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 820–827 (2002)

  15. Klein, P. N., Mozes, S., Sommer, C.: Structured recursive separator decompositions for planar graphs in linear time. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC), pp. 505–514 (2013). https://doi.org/10.1145/2488608.2488672

  16. Li, M., Ma, C. C. C., Ning, L.: (1 + 𝜖)-distance oracles for vertex-labeled planar graphs. In: Proceedings of the 10th International Conference on Theory and Applications of Models of Computation, 10th International Conference (TAMC), pp. 42–51 (2013)

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

    Article  MathSciNet  MATH  Google Scholar 

  18. Łȧcki, J., Oćwieja, J., Pilipczuk, M., Sankowski, P., Zych, A.: The power of dynamic distance oracles: Efficient dynamic algorithms for the Steiner tree. In: Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC), pp. 11–20 (2015)

  19. Mozes, S., Skop, E.E.: Efficient vertex-label distance oracles for planar graphs. In: Proceedings of the 13th International Workshop on Approximation and Online Algorithms (WAOA), pp. 97–109 (2015). https://doi.org/10.1007/978-3-319-28684-6_9

  20. Patrascu, M., Roditty, L.: Distance oracles beyond the Thorup-Zwick bound. SIAM J. Comput. 43(1), 300–311 (2014). https://doi.org/10.1137/11084128X

    Article  MathSciNet  MATH  Google Scholar 

  21. Ružić, M.: Constructing efficient dictionaries in close to sorting time. In: Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), pp. 84–95 (2008). https://doi.org/10.1007/978-3-540-70575-8_8

  22. von Staudt, K. G. C.: Geometrie der Lage. Bauer und Raspe, Nürnberg (1847)

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

    Article  MathSciNet  MATH  Google Scholar 

  24. Thorup, M., Zwick, U.: Approximate distance oracles. J. ACM 52(1), 1–24 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  25. Willard, D. E.: Log-logarithmic worst-case range queries are possible in space 𝜃(n). Inf. Process. Lett. 17(2), 81–84 (1983). https://doi.org/10.1016/0020-0190(83)90075-3

    Article  MathSciNet  MATH  Google Scholar 

  26. Wulff-Nilsen, C.: Approximate distance oracles with improved preprocessing time. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 202–208 (2012)

Download references

Acknowledgments

This work was partially supported by Israel Science Foundation grants 794/13 and 592/17, and by the Israeli ministry of absorption.

Author information

Authors and Affiliations

  1. Efi Arazi School of Computer Science, The Interdisciplinary Center Herzliya, Herzliya, Israel

    Shay Mozes & Eyal E. Skop

Authors
  1. Shay Mozes
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Eyal E. Skop
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Shay Mozes.

Additional information

An extended abstract of this work was presented in the 13th Workshop on Approximation and Online Algorithms (WAOA 2015), held in Patras, Greece, 17-18 September 2015.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Mozes, S., Skop, E.E. Efficient Vertex-Label Distance Oracles for Planar Graphs. Theory Comput Syst 62, 419–440 (2018). https://doi.org/10.1007/s00224-017-9827-0

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00224-017-9827-0

Keywords

Search

Navigation