DYNAMIC REACHABILITY IN PLANAR DIGRAPHS WITH ONE SOURCE AND ONE SINK

In this paper we investigate the reachability problem on spherical st- graphs. which are planar acyclic digraphs with exactly one source and exactly one sink. These digraphs find specific applications to visibil ity representations, planarity testing, planar graph embedding, graph drawing, and motion planning. Let n be the number of vertices. First, we show that reachability queries in a spherical st-graph can be answe red in O(1) time using an O(n)-space data structure that can be constr ucted in O(n) time. Next, we present a dynamic data structure, which u ses O(n) space and supports reachability queries and updates in O(log n) time. Finally, we show how to extend these results to planar digrap hs that have one source and one sink and may have directed cycles.