Constant Query Time $(1+\epsilon )$-Approximate Distance Oracle for Planar Graphs

Qian-Ping Gu, Gengchun Xu

We give a $(1+\epsilon )$-approximate distance oracle with $O(1)$ query time for an undirected planar graph $G$ with $n$ vertices and non-negative edge lengths. For $\epsilon >0$ and any two verti…