DYNAMIC ALGORITHMS FOR SHORTEST PATHS IN PLANAR GRAPHS

We propose data structures for maintaining shortest paths in planar graphs in which the weight of an edge is modified. Our data structures allow us to compute, after an update, the shortest-path tree rooted at an arbitrary query node in time O(n square-root log log n) and to perform an update in O((log n)3). Our data structure can be applied also to the problem of maintaining the maximum flow problem in an s-t planar network. As far as the all-pairs shortest-path problem is concerned. we are interested in computing the shortest distances between q pairs of nodes. We show how to obtain an o(n2) algorithm for computing the shortest path between q pairs of nodes whenever q=o(n2). We also consider the dynamic version of the problem in which we allow the modification of the weight of an edge.