Shay Mozes: Almost Optimal Distance Oracles for Planar Graphs

We present new tradeoffs between space and query-time for exact distance oracles in directed weighted planar graphs.
These tradeoffs are almost optimal in the sense that they are within polylogarithmic, sub-polynomial or arbitrarily small polynomial factors from the naive linear space, constant query-time lower bound.
These tradeoffs include:  
(i) an oracle with space O(n^{1+\epsilon}) and query-time ~O(1) for any constant \epsilon>0,
(ii) an oracle with space ~O(n) and query-time O(n^{\epsilon}) for any constant \epsilon>0, and
(iii) an oracle with space n^{1+o(1)} and query-time n^{o(1)}. 

Joint work with Panagiotis Charalampopoulos, Pawel Gawrychoski and Oren Weimann