Fully Dynamic Techniques for Reachability in Planar sT-graphs

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 ) $.