Tech Report CS-91-02

Fully Dynamic Techniques for Reachability in Planar sT-graphs

S. Sairam, Robert F. Cohen, Roberto Tamassia and Jeffrey S. Vitter

December 1990

Abstract:

We present fully dynamic techniques to solve the reachability problem in single-source multi-sink planar {\em st-}graphs ({\em sT-}graphs). We provide an {\em O(n)} space data structure which supports transitive closure queries in $O( \log ^ 2 n )$ time. We then show how to maintain this data structure under updates (insertion of an edge and expansion of a vertex, and their inverses) to the graph {\em G}, in time $O ( \log n ) $.

(complete text in pdf)