Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels
Résumé
This paper considers fully dynamic (1 + ε) distance oracles and (1 + ε) forbidden-set labeling schemes for pla- nar 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 log2 n log (nM ) * (ε−1 + log n)). 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. We then present a general method to transform (1 + ε) forbidden-set labeling schemas into a fully dynamic (1 + ε) distance oracle. Our fully dynamic (1 + ε) distance oracle is of size O(n log n * (ε−1 + log n)) and has O ̃(n1/2) query and update time, both the query and the update time are worst case. This improves on the best previously known (1 + ε) dynamic distance oracle for planar graphs, which has worst case query time O ̃(n2/3) and amortized update time of O ̃(n2/3). Our (1 + ε) forbidden-set labeling scheme can also be extended into a forbidden-set labeled routing scheme with stretch (1 + ε).