2018/07/16 by Panagiotis Charalampopoulos, Shay Mozes, Charalampopoulos, Panagiotis +3
Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1807.05968
openalex publication_date 2018/07/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 O(n)-size, O(√(n))-query-time oracle. We then present a space vs. query time tradeoff: for any q ∈ \lbrack 1,√ n \rbrack, we propose an oracle of size nk+1+o(1)/q2k that answers queries in O(q) time. For single vertex failures (k=1), our n2+o(1)/q2-size, O(q)-query-time oracle improves over the previously best known tradeoff of Baswana et al. [SODA 2012] by polynomial factors for q ≥ nt, for any t ∈ (0,1/2]. For multiple failures, no planarity exploiting results were previously known. A preliminary version of this work was presented in SODA 2019. In this version, we show improved space vs. query time tradeoffs relying on the recently proposed almost optimal distance oracles for planar graphs [Charalampopoulos et al., STOC 2019; Long and Pettie, SODA 2021].