Optimal Approximate Distance Oracle for Planar Graphs
Optimal Approximate Distance Oracle for Planar Graphs
A ( <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$1+\epsilon$</tex> ) -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 ( <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$1+\epsilon$</tex> ) factor. Thorup (FOCS 2001, JACM 2004) and Klein (SODA 2002) independently constructed a …