Optimal Approximate Distance Oracle for Planar Graphs

A ($1+\epsilon$) -approximate distance oracle of an edge-weighted graph is a data structure that returns an approximate shortest path distance between any two query vertices up to a ($1+\epsilon$) factor. Thorup (FOCS 2001, JACM 2004) and Klein (SODA 2002) independently constructed a ($1+\epsilon$) -approximate distance oracle with$O(n\log n)$space, measured in number of words, and$O(1)$query time when$G$is an undirected planar graph with$n$vertices and$\epsilon$is a fixed constant. Many follow-up works gave ($1+\epsilon$) -approximate distance oracles with various trade-offs between space and query time. However, improving$O(n\log n)$space bound without sacrificing query time remains an open problem for almost two decades. In this work, we resolve this problem affirmatively by constructing a ($1+\epsilon$) approximate distance oracle with optimal$O(n)$space and$O(1)$query time for undirected planar graphs and fixed$\epsilon$. We also make substantial progress for planar digraphs with non-negative edge weights. For fixed$\epsilon > 0$, we give a ($1+\epsilon$) -approximate distance oracle with space$o(n\log(Nn))$and$O(\log\log(Nn)$query time; here$N$is the ratio between the largest and smallest positive edge weight. This improves Thorup's (FOCS 2001, JACM 2004)$O(n\log(Nn)\log n)$space bound by more than a logarithmic factor while matching the query time of his structure. This is the first improvement for planar digraphs in two decades, both in the weighted and unweighted setting.