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.