2015 | OriginalPaper | Buchkapitel
Efficient Vertex-Label Distance Oracles for Planar Graphs
Erschienen in:
Approximation and Online Algorithms
Abstract
We consider distance queries in vertex labeled planar graphs. For any fixed \(0 < \epsilon \le 1/2\) we show how to preprocess an undirected planar graph with vertex labels and edge lengths to answer queries of the following form. Given a vertex u and a label \(\lambda \) return a \((1+\epsilon )\)-approximation of the distance between u and its closest vertex with label \(\lambda \). The query time of our data structure is \(O(\lg \lg {n} + \epsilon ^{-1})\), where n is the number of vertices. The space and preprocessing time of our data structure are nearly linear. We give a similar data structure for directed planar graphs with slightly worse performance. The best prior result for the undirected case has similar space and preprocessing bounds, but exponentially slower query time. No nontrivial results were previously considered for the directed case.
