# ACG12

### Summary

**Abraham, Ittai, Chechik, Shiri and Gavoille, Cyril** (2012) *Fully Dynamic Approximate Distance Oracles for Planar Graphs via Forbidden-Set Distance Labels.* In {$44^{th}$} Annual ACM Symposium on Theory of Computing (STOC). may. ACM Press, pages 1199-1218. ((URL)) (PDF)

### Abstract

This paper considers fully dynamic {$(1+\varepsilon)$} distance oracles and {$(1+\varepsilon)$} forbidden-set labeling schemes for planar graphs. For a given {$n$}-vertex planar graph {$G$} with edge weights drawn from {1,M$} and parameter {$\varepsilon>0$}, our forbidden-set labeling scheme uses labels of length {$\lambda = O({\varepsilon}^{-1}\log^2{n} \log{(nM)} \cdot ({\varepsilon}^{-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\setminus F$} with stretch {$(1+\varepsilon)$}, in {$O(|F|^2 \lambda)$} time. We then present a general method to transform {$(1+\varepsilon)$} forbidden-set labeling schemes into a fully dynamic {$(1+\varepsilon)$} distance oracle. Our fully dynamic {$(1+\varepsilon)$} distance oracle is of size {$O(n \log{n} \cdot ({\varepsilon}^{-1}+\log{n}))$} and has {$\tilde{O}(n^{1/2})$} query and update time, both the query and the update time are worst case. This improves on the best previously known {$(1+\varepsilon)$} dynamic distance oracle for planar graphs, which has worst case query time {$\tilde{O}(n^{2/3})$} and amortized update time of {$\tilde{O}(n^{2/3})$}. Our {$(1+\varepsilon)$} forbidden-set labeling scheme can also be extended into a forbidden-set labeled routing scheme with stretch {$(1+\varepsilon)$}.

### Bibtex entry

`@INPROCEEDINGS { ACG12,`

AUTHOR = { Abraham, Ittai and Chechik, Shiri and Gavoille, Cyril },

TITLE = { Fully Dynamic Approximate Distance Oracles for Planar Graphs via Forbidden-Set Distance Labels },

BOOKTITLE = { {$44^{th}$} Annual ACM Symposium on Theory of Computing (STOC) },

PUBLISHER = { ACM Press },

LOCATION = { New York, NY, USA },

MONTH = { may },

YEAR = { 2012 },

PAGES = { 1199-1218 },

URL = { http://dx.doi.org/10.1145/2213977.2214084 },

DOI = { 10.1145/2213977.2214084 },

PDF = { http://dept-info.labri.fr/~gavoille/article/ACG12.pdf },

KEYWORDS = { data-structure, dynamic, planar, compact routing },

ABSTRACT = { This paper considers fully dynamic {$(1+\varepsilon)$} distance oracles and {$(1+\varepsilon)$} forbidden-set labeling schemes for planar graphs. For a given {$n$}-vertex planar graph {$G$} with edge weights drawn from {1,M$} and parameter {$\varepsilon>0$}, our forbidden-set labeling scheme uses labels of length {$\lambda = O({\varepsilon}^{-1}\log^2{n} \log{(nM)} \cdot ({\varepsilon}^{-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\setminus F$} with stretch {$(1+\varepsilon)$}, in {$O(|F|^2 \lambda)$} time. We then present a general method to transform {$(1+\varepsilon)$} forbidden-set labeling schemes into a fully dynamic {$(1+\varepsilon)$} distance oracle. Our fully dynamic {$(1+\varepsilon)$} distance oracle is of size {$O(n \log{n} \cdot ({\varepsilon}^{-1}+\log{n}))$} and has {$\tilde{O}(n^{1/2})$} query and update time, both the query and the update time are worst case. This improves on the best previously known {$(1+\varepsilon)$} dynamic distance oracle for planar graphs, which has worst case query time {$\tilde{O}(n^{2/3})$} and amortized update time of {$\tilde{O}(n^{2/3})$}. Our {$(1+\varepsilon)$} forbidden-set labeling scheme can also be extended into a forbidden-set labeled routing scheme with stretch {$(1+\varepsilon)$}. },

}