# Fast and Compact Exact Distance Oracle for Planar Graphs

arXiv: https://arxiv.org/abs/1702.03259 · HTML: https://mlsanity.com/paper/1702.03259/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Feb 2017.

## Built on by (most cited first, 1 of 1)

- [Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach](https://mlsanity.com/paper/2509.05129/) (2025)

## Abstract (arXiv)

For a given a graph, a distance oracle is a data structure that answers distance queries between pairs of vertices. We introduce an O(n5/3)-space distance oracle which answers exact distance queries in O(log n) time for n-vertex planar edge-weighted digraphs. All previous distance oracles for planar graphs with truly subquadratic space i.e., space O(n2 - ε) for some constant ε > 0) either required query time polynomial in n or could only answer approximate distance queries. Furthermore, we show how to trade-off time and space: for any S ≥ n3/2, we show how to obtain an S-space distance oracle that answers queries in time O((n5/2/ S3/2) log n). This is a polynomial improvement over the previous planar distance oracles with o(n1/4) query time.