We consider distance queries in vertex labeled planar graphs. For any fixed $0 < \varepsilon \leq 1/2$ we show how to preprocess a planar graph with vertex labels and edge lengths into a data structure that answers queries of the following form. Given a vertex $u$ and a label $\lambda$ return a $(1+O(\varepsilon))$-approximation of the distance between $u$ and its closest vertex with label $\lambda$.
For an undirected $n$-vertex planar graph the preprocessing time is $O(\varepsilon^{-2}n\lg^{3}{n})$, the size is $O(\varepsilon^{-1}n\lg{n})$, and the query time is $O(\log\log{n} + \varepsilon^{-1})$.
For a directed planar graph with arc lengths bounded by $N$, the preprocessing time is $O(\varepsilon^{-2}n\lg^{3}{n}\lg(nN))$, the data structure size is $O(\varepsilon^{-1}n\lg{n}\lg(nN))$, and the query time is $O(\log\log{n}\log\log(nN) + \varepsilon^{-1})$.
Eyal Skop, IDC Herzliya