On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs

Given a base weighted planar graph G_input on n nodes and parameters M, epsilon we present a dynamic distance oracle with 1+epsilon stretch and worst case update and query costs of epsilon^{−3}M^4 · poly-log(n). We allow arbitrary edge weight updates as long as the shortest path metric induced by the updated graph has stretch of at most M relative to the shortest path metric of the base graph G_input. For example, on a planer road network, we can support fast queries and dynamic traffic updates as long as the shortest path from any source to any target (including using arbitrary detours) is between, say, 80 and 3 miles-per-hour. As a warm-up we also prove that graphs of bounded treewidth have exact distance oracles in the dynamic edge model. To the best of our knowledge, this is the first dynamic distance oracle for a non-trivial family of dynamic changes to planar graphs with worst case costs of o(n ½ ) both for query and for update operations.

Joint work with Shiri Chechik, Daniel Delling, Andrew Goldberg and Renato Werneck.