Document Open Access Logo

Near-Optimal Distance Oracles for Vertex-Labeled Planar Graphs

Authors Jacob Evald, Viktor Fredslund-Hansen , Christian Wulff-Nilsen

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2021.23.pdf
  • Filesize: 1.15 MB
  • 14 pages

Document Identifiers

Author Details

Jacob Evald
  • Department of Computer Science, University of Copenhagen, Denmark
Viktor Fredslund-Hansen
  • Department of Computer Science, University of Copenhagen, Denmark
Christian Wulff-Nilsen
  • Department of Computer Science, University of Copenhagen, Denmark

Funding

  • Evald, Jacob: This research is supported by the Starting Grant 7027-00050B from the Independent Research Fund Denmark under the Sapere Aude research career programme.
  • Fredslund-Hansen, Viktor: This research is supported by the Starting Grant 7027-00050B from the Independent Research Fund Denmark under the Sapere Aude research career programme.
  • Wulff-Nilsen, Christian: This research is supported by the Starting Grant 7027-00050B from the Independent Research Fund Denmark under the Sapere Aude research career programme and by Basic Algorithms Research Copenhagen (BARC).

Acknowledgements

We are grateful for the thorough and useful feedback provided by the reviewers.

Cite As Get BibTex

Jacob Evald, Viktor Fredslund-Hansen, and Christian Wulff-Nilsen. Near-Optimal Distance Oracles for Vertex-Labeled Planar Graphs. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ISAAC.2021.23

Abstract

Given an undirected n-vertex planar graph G = (V,E,ω) with non-negative edge weight function ω:E → ℝ and given an assigned label to each vertex, a vertex-labeled distance oracle is a data structure which for any query consisting of a vertex u and a label λ reports the shortest path distance from u to the nearest vertex with label λ. We show that if there is a distance oracle for undirected n-vertex planar graphs with non-negative edge weights using s(n) space and with query time q(n), then there is a vertex-labeled distance oracle with Õ(s(n)) space and Õ(q(n)) query time. Using the state-of-the-art distance oracle of Long and Pettie [Long and Pettie, 2021], our construction produces a vertex-labeled distance oracle using n^{1+o(1)} space and query time Õ(1) at one extreme, Õ(n) space and n^o(1) query time at the other extreme, as well as such oracles for the full tradeoff between space and query time obtained in their paper. This is the first non-trivial exact vertex-labeled distance oracle for planar graphs and, to our knowledge, for any interesting graph class other than trees.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
  • Theory of computation → Shortest paths
  • Mathematics of computing → Graph algorithms
Keywords
  • distance oracle
  • vertex labels
  • color distance oracle
  • planar graph

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup. Maintaining information in fully dynamic trees with top trees. ACM Trans. Algorithms, 1(2):243-264, October 2005. URL: https://doi.org/10.1145/1103963.1103966.
  2. Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes, and Oren Weimann. Almost optimal distance oracles for planar graphs. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 138-151, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3313276.3316316.
  3. Shiri Chechik. Improved distance oracles and spanners for vertex-labeled graphs. In Leah Epstein and Paolo Ferragina, editors, Algorithms - ESA 2012, pages 325-336, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Google Scholar
  4. H. Davenport and A. Schinzel. A Combinatorial Problem Connected with Differential Equations. American Journal of Mathematics, 87(3):684, July 1965. URL: https://doi.org/10.2307/2373068.
  5. James R. Driscoll, Neil Sarnak, Daniel D. Sleator, and Robert E. Tarjan. Making data structures persistent. Journal of Computer and System Sciences, 38(1):86-124, 1989. URL: https://doi.org/10.1016/0022-0000(89)90034-2.
  6. Jeff Erickson, Kyle Fox, and Luvsandondov Lkhamsuren. Holiest minimum-cost paths and flows in surface graphs. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 1319-1332. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188904.
  7. Paweł Gawrychowski, Shay Mozes, Oren Weimann, and Christian Wulff-Nilsen. Better tradeoffs for exact distance oracles in planar graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pages 515-529, USA, 2018. Society for Industrial and Applied Mathematics. Google Scholar
  8. Paweł Gawrychowski, Gad M. Landau, Shay Mozes, and Oren Weimann. The nearest colored node in a tree. Theoretical Computer Science, 710:66-73, 2018. URL: https://doi.org/10.1016/j.tcs.2017.08.021.
  9. Danny Hermelin, Avivit Levy, Oren Weimann, and Raphael Yuster. Distance oracles for vertex-labeled graphs. In Luca Aceto, Monika Henzinger, and Jiří Sgall, editors, Automata, Languages and Programming, pages 490-501, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. Google Scholar
  10. Philip Klein. Multiple-source shortest paths in planar graphs. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pages 146-155, January 2005. Google Scholar
  11. Mingfei Li, Chu Chung Christopher Ma, and Li Ning. (1+ε)-distance oracles for vertex-labeled planar graphs. In T-H. Hubert Chan, Lap Chi Lau, and Luca Trevisan, editors, Theory and Applications of Models of Computation, pages 42-51, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. Google Scholar
  12. Yaowei Long and Seth Pettie. Planar Distance Oracles with Better Time-Space Tradeoffs. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2517-2537. Society for Industrial and Applied Mathematics, Philadelphia, PA, January 2021. URL: https://doi.org/10.1137/1.9781611976465.149.
  13. Shay Mozes and Eyal E. Skop. Efficient Vertex-Label Distance Oracles for Planar Graphs. Theory of Computing Systems, 62(2):419-440, February 2018. URL: https://doi.org/10.1007/s00224-017-9827-0.
  14. Maximilian Probst. On the Complexity of the (Approximate) Nearest Colored Node Problem. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms (ESA 2018), volume 112 of Leibniz International Proceedings in Informatics (LIPIcs), pages 68:1-68:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.68.
  15. Dekel Tsur. Succinct data structures for nearest colored node in a tree. Information Processing Letters, 132:6-10, 2018. URL: https://doi.org/10.1016/j.ipl.2017.10.001.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact