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. 1 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 2 -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.

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. More specifically, for a directed weighted planar graph with n vertices, any constant k, and for any q ∊ [1, ], we propose an oracle of size that answers queries in Õ(q) time.1 In particular, we show an Õ(n)-size, -query-time oracle for any constant k. This matches, up to polylogarithmic factors, the fastest failure-free distance oracles with nearly linear space. For single vertex failures (k = 1), our -size, Õ(q)-query-time oracle improves over the previously best known tradeoff of Baswana et al. [SODA 2012] by polynomial factors for q = Ω(nt), t ∊ (1/4, 1/2]. For multiple failures, no planarity exploiting results were previously known.