Improved algorithms for dynamic shortest paths

We describe algorithms for finding shortest paths and distances in outerpla nar and planar digraphs that exploit the particular topology of the input g raph. An important feature of our algorithms is that they can work in a dyn amic environment, where the cost of any edge can be changed or the edge can be deleted. In the case of outerplanar digraphs, our data structures can b e updated after any such change in only logarithmic time. A distance query is also answered in logarithmic time. In the case of planar digraphs, we gi ve an interesting tradeoff between preprocessing, query, and update times d epending on the value of a certain topological parameter of the graph. Our results can be extended to n-vertex digraphs of genus O(n(1-epsilon)) for a ny epsilon > 0.