This paper considers fully dynamic (1+{\epsilon}) distance oracles and (1+{\epsilon}) forbidden-set labeling schemes for planar graphs. For a given n-vertex planar graph G with edge weights drawn from [1,M] and parameter {\epsilon}>0, our forbidden-set labeling scheme uses labels of length {\lambda} = O({\epsilon}-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+{\epsilon}), in O(|F|2 {\lambda}) time.

We then present a general method to transform (1+{\epsilon}) forbidden-set labeling schemas into a fully dynamic (1+{\epsilon}) distance oracle. Our fully dynamic (1+{\epsilon}) distance oracle is of size O(n logn • maxlogn) and has {\tilde}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+{\epsilon}) dynamic distance oracle for planar graphs, which has worst case query time {\tilde}O(n2/3) and amortized update time of {\tilde}O(n2/3).

Our (1+{\epsilon}) forbidden-set labeling scheme can also be extended into a forbidden-set labeled routing scheme with stretch (1+{\epsilon}).

}, author = {Ittai Abraham and Shiri Chechik and Cyril Gavoille}, booktitle = {STOC '12 Proceedings of the 44th symposium on Theory of Computing}, title = {Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels}, url = {http://research.microsoft.com/apps/pubs/default.aspx?id=163401}, year = {2012}, }