Efficient Vertex-Label Distance Oracles for Planar Graphs

摘要

Abstract We consider distance queries in vertex-labeled planar graphs. For any fixed 0 ?? ≤?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 λ return a (1 + ?? )-approximation of the distance from u to its closest vertex with label λ . 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 ( ?? ??2 n lg 3 n lg( n N )), the data structure size is O ( ?? ??1 n lg n lg( n N )), and the query time is O (lg lg n lg lg( n N ) + ?? ??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.