Efficient Vertex-Label Distance Oracles for Planar Graphs

摘要

We consider distance queries in vertex-labeled planar graphs. For any fixed 0 oee- aecurrency 1/2 we show how to preprocess a directed planar graph with vertex labels and arc lengths into a data structure that answers queries of the following form. Given a vertex u and a label lambda return a (1 + oee-)-approximation of the distance from u to its closest vertex with label lambda. For a directed planar graph with n vertices, such that the ratio of the largest to smallest arc length is bounded by N, the preprocessing time is O(oee- (- 2) n lg 3n lg(n N)), the data structure size is O(oee- (- 1) n lg n lg(n N)), and the query time is O(lg lg n lg lg(n N) + oee- (- 1)). We also point out that a vertex label distance oracle for undirected planar graphs suggested in an earlier version of this paper is incorrect.