Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels
Ittai Abraham, Shiri Chechik, Cyril Gavoille · 2012
This paper considers fully dynamic (1+ε) distance oracles and (1+ε) forbidden-set labeling schemes for planar graphs. For a given n-vertex planar graph G with edge weights drawn from [1,M] and parameter ε>0, our forbidden-set labeling scheme uses labels of length λ = O(ε-1 log2n log(nM) • maxlogn). Given the labels of two vertices s and t and of a set F of faulty vertices/edges, our scheme approximates the distance between s and t in G \ F with stretch (1+ε), in O(|F|2 λ) time.