Shortest path queries in planar graphs

The problem of processing shortest path queries in graphs arises in application areas such as intelligent transportation system (ITS), geographic information system (GIS), and robotics. In this paper, we present an efficient algorithmic solution for processing shortest path queries in undirected planar graphs with non-negative edge weights. Previous algorithms for this problem on planar graphs all have a tradeoff between the query time and the data structure space used by the solutions. The previously best known trade-off on an n-vertex planar graph G in the worst case is O(√r) time for a path length query and O(√r + L) time for reporting an actual shortest path, with a data structure of O(n²/√r) space, where r is an integer parameter with 1 ≤ r ≤ n and L is the number of edges on the output shortest path. We present a new scheme, called frame search, that exploits the graph planarity in a novel fashion. With this scheme, we build an improved data structure of O(n + p√r + p²/r) space (in O(n + p²/√r + pr ^3/4) time), where p is the minimum cardinality of a face-covering of the planar embedding of G with 1 ≤ p ≤ Θ(n), and r is an integer parameter with 1 ≤ r ≤ p. This data structure enables us to process each length query in O(√r log r + α(n)) time and report an actual shortest path in an additional O(L) time, where α(n) is the inverse of Ackermann's function. In the worst case, our approach reduces the previously best query time by a factor of up to O(n^1/4) if the same amount of space is used. Our technique can also be applied to improve the previous query algorithms for some geometric shortest path problems on the plane.