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 time a data structure of size O(S) that answers distance queries in time per query. As a consequence, we obtain an improvement over the fastest algorithm for k-many distances in planar graphs whenever .
- We provide a linear-space exact distance oracle for planar graphs with query time for any constant . This is the first such data structure with provable sublinear query time.
- For edge lengths , we provide an exact distance oracle of space such that for any pair of nodes at distance the query time is . 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 nodes, we can preprocess G in time to produce a data structure of size that can answer the following queries in 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 and space , we essentially improve the query time from to .
Guest: Shay Mozes
Host: Shantanu Das