# Exact Distance Oracles for Planar Graphs

## Shay Mozes and Christian Sommer

Abstract:

We present new and improved data structures that answer exact node-to-node distance queries in planar graphs. Such data structures are also known as distance oracles. For any directed planar graph on n nodes with non-negative lengths we obtain the following:

• Given a desired space allocation S \in $n \log\log n, n^2$, we show how to construct in $\~{O}(S)$ time a data structure of size O(S) that answers distance queries in $\~{O}(n/\sqrt{S})$ time per query. As a consequence, we obtain an improvement over the fastest algorithm for k-many distances in planar graphs whenever $k \in \[\sqrt{n},n)$.
• We provide a linear-space exact distance oracle for planar graphs with query time $O(n^{1/2+\epsilon})$ for any constant $\epsilon > 0$. This is the first such data structure with provable sublinear query time.
• For edge lengths $\geq 1$, we provide an exact distance oracle of space $\~{O}(n)$ such that for any pair of nodes at distance $l$ the query time is $\~{O} (min\{l,\sqrt{n}\})$. Comparable query performance had been observed experimentally but could not be proven.

Our data structures are based on the following new tool: given a non-self-crossing cycle C with $c = O(\sqrt{n})$ nodes, we can preprocess G in $\~{O}(n)$ time to produce a data structure of size $O(n \log{\log{c}})$ that can answer the following queries in $\~{O}(c)$ time: for a query node u, output the distance from u to all the nodes of C. This data structure builds on and extends a related data structure of Klein (SODA’05), which reports distances to the boundary of a face, rather than a cycle.
The best distance oracles for planar graphs until the current work are due to Cabello (SODA’06), Djidjev (WG’96), and Fakcharoenphol and Rao (FOCS’01). For $\sigma \in (1, \sfrac{4}{3})$ and space $S = n^\sigma$, we essentially improve the query time from $n^2/S$ to $\sqrt{n^2/S}$.

Guest: Shay Mozes
Host: Shantanu Das