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, subpolynomial 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+ε) and query-time Õ(1) for any constant ε>0, (ii) an oracle with space Õ(n) and query-time Ο(n^ε) for any constant ε >0, and (iii) an oracle with space n^1+ο(1) and query-time n^ο(1).

Joint work with P. Gawrychowski, S. Mozes and O. Weimann.