More Web Proxy on the site http://driver.im/

research-article

Exact Distance Oracles for Planar Graphs with Failing Vertices

Authors:

Panagiotis Charalampopoulos,

Benjamin TebekaAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 18, Issue 2

Article No.: 18, Pages 1 - 23

https://doi.org/10.1145/3511541

Published: 30 March 2022 Publication History

Abstract

We consider exact distance oracles for directed weighted planar graphs in the presence of failing vertices. Given a source vertex u, a target vertex v and a set X of k failed vertices, such an oracle returns the length of a shortest u-to-v path that avoids all vertices in X. We propose oracles that can handle any number k of failures. We show several tradeoffs between space, query time, and preprocessing time. In particular, for a directed weighted planar graph with n vertices and any constant k, we show an Õ(n)-size, Õ(√ n)-query-time oracle. We then present a space vs. query time tradeoff: for any q ε [ 1,√ n ], we propose an oracle of size n^k+1+o(1)/q^2k that answers queries in Õ(q) time. For single vertex failures (k = 1), our n^2+o(1)/q²-size, Õ(q)-query-time oracle improves over the previously best known tradeoff of Baswana et al. SODA 2012 by polynomial factors for q ≥ n^t, for any t ∈ (0,1/2]. For multiple failures, no planarity exploiting results were previously known.

References

[1]

Amir Abboud and Søren Dahlgaard. 2016. Popular conjectures as a barrier for dynamic planar graph algorithms. In 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016. 477–486.

[2]

Ittai Abraham, Shiri Chechik, and Cyril Gavoille. 2012. Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. In 44th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2012. 1199–1218.

Digital Library

[3]

Srinivasa Rao Arikati, Danny Z. Chen, L. Paul Chew, Gautam Das, Michiel H. M. Smid, and Christos D. Zaroliagis. 1996. Planar spanners and approximate shortest path queries among obstacles in the plane. In 4th Annual European Symposium on Algorithms, ESA 1996. 514–528.

[4]

Aviv Bar-Natan, Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes, and Oren Weimann. 2021. Fault-tolerant distance labeling for planar graphs. In 28th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2021. 315–333.

Digital Library

[5]

Surender Baswana, Utkarsh Lath, and Anuradha S. Mehta. 2012. Single source distance oracle for planar digraphs avoiding a failed node or link. In 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. 223–232.

[6]

Aaron Bernstein and David R. Karger. 2009. A nearly optimal oracle for avoiding failed vertices and edges. In 41st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2009. 101–110.

Digital Library

[7]

Glencora Borradaile, Piotr Sankowski, and Christian Wulff-Nilsen. 2015. Min st-cut oracle for planar graphs with near-linear preprocessing time. ACM Trans. Algorithms 11, 3 (2015), 16:1–16:29.

Digital Library

[8]

Sergio Cabello. 2012. Many distances in planar graphs. Algorithmica 62, 1–2 (2012), 361–381.

Digital Library

[9]

Sergio Cabello, Erin W. Chambers, and Jeff Erickson. 2013. Multiple-source shortest paths in embedded graphs. SIAM J. Comput. 42, 4 (2013), 1542–1571.

Digital Library

[10]

Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes, and Oren Weimann. 2019. Almost optimal distance oracles for planar graphs. In 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019. 138–151.

Digital Library

[11]

Panagiotis Charalampopoulos and Adam Karczmarz. 2020. Single-source shortest paths and strong connectivity in dynamic planar graphs. In 28th Annual European Symposium on Algorithms, ESA 2020. 31:1–31:23.

[12]

Panagiotis Charalampopoulos, Shay Mozes, and Benjamin Tebeka. 2019. Exact distance oracles for planar graphs with failing vertices. In 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019. 2110–2123.

[13]

Danny Z. Chen and Jinhui Xu. 2000. Shortest path queries in planar graphs. In 32nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2000. 469–478.

Digital Library

[14]

Vincent Cohen-Addad, Søren Dahlgaard, and Christian Wulff-Nilsen. 2017. Fast and compact exact distance oracle for planar graphs. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017. 962–973.

[15]

Camil Demetrescu, Mikkel Thorup, Rezaul Alam Chowdhury, and Vijaya Ramachandran. 2008. Oracles for distances avoiding a failed node or link. SIAM J. Comput. 37, 5 (2008), 1299–1318.

Digital Library

[16]

Hristo Djidjev. 1996. On-line algorithms for shortest path problems on planar digraphs. In 22nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1996. 151–165.

[17]

Ran Duan and Seth Pettie. 2009. Dual-failure distance and connectivity oracles. In 20th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009. 506–515. http://dl.acm.org/citation.cfm?id=1496770.1496826.

[18]

Ran Duan and Hanlin Ren. 2021. Maintaining exact distances under multiple edge failures. CoRR abs/2111.03360 (2021). arXiv:2111.03360 https://arxiv.org/abs/2111.03360.

[19]

Yuval Emek, David Peleg, and Liam Roditty. 2010. A near-linear-time algorithm for computing replacement paths in planar directed graphs. ACM Trans. Algorithms 6, 4 (2010), 64:1–64:13.

Digital Library

[20]

David Eppstein. 1998. Finding the k shortest paths. SIAM J. Comput. 28, 2 (1998), 652–673.

Digital Library

[21]

Jeff Erickson, Kyle Fox, and Luvsandondov Lkhamsuren. 2018. Holiest minimum-cost paths and flows in surface graphs. In 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018. 1319–1332.

Digital Library

[22]

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

Digital Library

[23]

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

Digital Library

[24]

Viktor Fredslund-Hansen, Shay Mozes, and Christian Wulff-Nilsen. 2021. Truly subquadratic exact distance oracles with constant query time for planar graphs. In 32nd International Symposium on Algorithms and Computation, ISAAC 2021. 25:1–25:12.

[25]

Paweł Gawrychowski, Haim Kaplan, Shay Mozes, Micha Sharir, and Oren Weimann. 2021. Voronoi diagrams on planar graphs, and computing the diameter in deterministic Õ(n\({}^{\mbox{5/3}}\)) time. SIAM J. Comput. 50, 2 (2021), 509–554.

Digital Library

[26]

Paweł Gawrychowski and Adam Karczmarz. 2018. Improved bounds for shortest paths in dense distance graphs. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018. 61:1–61:15.

[27]

Paweł Gawrychowski, Shay Mozes, Oren Weimann, and Christian Wulff-Nilsen. 2018. Better tradeoffs for exact distance oracles in planar graphs. In 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. 515–529.

[28]

John Hershberger and Subhash Suri. 2001. Vickrey prices and shortest paths: What is an edge worth? In 42nd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2001. 252–259.

[29]

Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen. 2011. Improved algorithms for min cut and max flow in undirected planar graphs. In 43rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2011. 313–322.

Digital Library

[30]

Haim Kaplan, Shay Mozes, Yahav Nussbaum, and Micha Sharir. 2017. Submatrix maximum queries in Monge matrices and partial Monge matrices, and their applications. ACM Trans. Algorithms 13, 2 (2017), 26:1–26:42.

Digital Library

[31]

Young-Jin Kim, Ramesh Govindan, Brad Karp, and Scott Shenker. 2005. Geographic routing made practical. In 2nd Symposium on Networked Systems Design and Implementation (NSDI 2005). USENIX. http://www.usenix.org/events/nsdi05/tech/kim.html.

[32]

Philip N. Klein. 2005. Multiple-source shortest paths in planar graphs. In 16th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005. 146–155. http://dl.acm.org/citation.cfm?id=1070432.1070454.

[33]

Philip N. Klein, Shay Mozes, and Christian Sommer. 2013. Structured recursive separator decompositions for planar graphs in linear time. In 45th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2013. 505–514.

Digital Library

[34]

Philip N. Klein, Shay Mozes, and Oren Weimann. 2010. Shortest paths in directed planar graphs with negative lengths: A linear-space O(nlog\({}^{2}\)n)-time algorithm. ACM Trans. Algorithms 6, 2 (2010), 30:1–30:18.

Digital Library

[35]

Yaowei Long and Seth Pettie. 2021. Planar distance oracles with better time-space tradeoffs. In 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021. 2517–2537.

[36]

Gary L. Miller. 1984. Finding small simple cycle separators for 2-connected planar graphs. In 16th Annual ACM Symposium on Theory of Computing, STOC 1984. 376–382.

Digital Library

[37]

Gaspard Monge. 1781. Mémoire sur la théorie des déblais et des remblais. De l’Imprimerie Royale.

[38]

Shay Mozes and Christian Sommer. 2012. Exact distance oracles for planar graphs. In 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. 209–222.

[39]

Shay Mozes and Christian Wulff-Nilsen. 2010. Shortest paths in planar graphs with real lengths in O(nlog\({}^{2}\)n/loglogn) time. In 18th Annual European Symposium on Algorithms, ESA 2010, Part II. 206–217.

[40]

Noam Nisan and Amir Ronen. 1999. Algorithmic mechanism design (extended abstract). In 31st Annual ACM SIGACT Symposium on Theory of Computing, STOC 1999. 129–140.

Digital Library

[41]

Jan van den Brand and Thatchaphol Saranurak. 2019. Sensitive distance and reachability oracles for large batch updates. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019. 424–435.

[42]

Oren Weimann and Raphael Yuster. 2013. Replacement paths and distance sensitivity oracles via fast matrix multiplication. ACM Trans. Algorithms 9, 2 (2013), 14:1–14:13.

Digital Library

[43]

Christian Wulff-Nilsen. 2010. Solving the replacement paths problem for planar directed graphs in O(nlogn) time. In 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010. 756–765.

Cited By

Charalampopoulos PGawrychowski PLong YMozes SPettie SWeimann OWulff-Nilsen C(2023)Almost Optimal Exact Distance Oracles for Planar GraphsJournal of the ACM10.1145/358047470:2(1-50)Online publication date: 25-Mar-2023
https://dl.acm.org/doi/10.1145/3580474
Bar-Natan ACharalampopoulos PGawrychowski PMozes SWeimann O(2022)Fault-tolerant distance labeling for planar graphsTheoretical Computer Science10.1016/j.tcs.2022.03.020918:C(48-59)Online publication date: 29-May-2022
https://dl.acm.org/doi/10.1016/j.tcs.2022.03.020

Index Terms

Exact Distance Oracles for Planar Graphs with Failing Vertices
1. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Shortest paths

Recommendations

Almost Optimal Exact Distance Oracles for Planar Graphs
We consider the problem of preprocessing a weighted directed planar graph in order to quickly answer exact distance queries. The main tension in this problem is between space S and query time Q, and since the mid-1990s all results had polynomial time-...
Almost optimal distance oracles for planar graphs
STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

We present new tradeoffs between space and query-time for exact distance oracles in directed weighted planar graphs. These tradeoffs are almost optimal in the sense that they are within polylogarithmic, subpolynomial or arbitrarily small polynomial ...
Total domination in planar graphs of diameter two

MacGillivary and Seyffarth [G. MacGillivray, K. Seyffarth, Domination numbers of planar graphs, J. Graph Theory 22 (1996) 213-229] proved that planar graphs of diameter two have domination number at most three. Goddard and Henning [W. Goddard, M.A. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 18, Issue 2

April 2022

285 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/3514175

Editor:
Edith Cohen
Google Research, USA and Tel Aviv University, Israel

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 March 2022

Online AM: 08 February 2022

Accepted: 01 December 2021

Revised: 01 December 2021

Received: 01 October 2020

Published in TALG Volume 18, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Refereed

Funding Sources

Israel Science Foundation (ISF)

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
193
Total Downloads

Downloads (Last 12 months)35
Downloads (Last 6 weeks)2

Reflects downloads up to 29 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Charalampopoulos PGawrychowski PLong YMozes SPettie SWeimann OWulff-Nilsen C(2023)Almost Optimal Exact Distance Oracles for Planar GraphsJournal of the ACM10.1145/358047470:2(1-50)Online publication date: 25-Mar-2023
https://dl.acm.org/doi/10.1145/3580474
Bar-Natan ACharalampopoulos PGawrychowski PMozes SWeimann O(2022)Fault-tolerant distance labeling for planar graphsTheoretical Computer Science10.1016/j.tcs.2022.03.020918:C(48-59)Online publication date: 29-May-2022
https://dl.acm.org/doi/10.1016/j.tcs.2022.03.020

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

HTML Format

View this article in HTML Format.

Figures

Tables

Media

View full text|Download PDF

View Issue’s Table of Contents