DYNAMIC ALGORITHMS FOR SHORTEST PATHS IN PLANAR GRAPHS

We propose data structures for maintaining shortest paths in planar gr aphs in which the weight of an edge is modified. Our data structures a llow 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 perf orm an update in O((log n)3). Our data structure can be applied also t o 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 s hortest path between q pairs of nodes whenever q=o(n2). We also consid er the dynamic version of the problem in which we allow the modificati on of the weight of an edge.