2 papers
cs.DS2026
Distances in Planar Graphs are Almost for Free!
Shay Mozes, Daniel Prigan
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. Na…
cs.DS2025
Faster Construction of a Planar Distance Oracle with Ã(1) Query Time
Itai Boneh, Shay Golan, Shay Mozes +2
We show how to preprocess a weighted undirected -vertex planar graph in time, such that the distance between any pair of vertices can then be reported in $\t…