Distances in Planar Graphs are Almost for Free!
This provides a significant efficiency improvement for algorithms handling distances in planar graphs, which is incremental but impactful for computational geometry and network analysis.
The paper tackles the problem of constructing exact distance oracles for planar graphs, showing that it is possible to achieve near-linear preprocessing time and polylogarithmic query time without tradeoffs, improving from previous cubic-time methods.
We prove that, up to subpolynomial or polylogarithmic factors, there is no tradeoff between preprocessing time, query time, and size of exact distance oracles for planar graphs. Namely, we show how given an $n$-vertex weighted directed planar graph $G$, one can compute in $n^{1+o(1)}$ time and space a representation of $G$ from which one can extract the exact distance between any two vertices of $G$ in $\log^{2+o(1)}(n)$ time. Previously, it was only known how to construct oracles with these space and query time in $n^{3/2+o(1)}$ time [STOC 2019, SODA 2021, JACM 2023]. We show how to construct these oracles in $n^{1+o(1)}$ time.