The authors show the a planar st-graph G admits two total orders (called leftist and rightist, respectively) on a certain set where V, E, and F are respectively the set of vertices, edges, and faces of G, with V = n. Assuming that G is to be dynamically modified by means of insertions of edges and expansions of vertices (and their inverses), we exhibit a O(n)-space dynamic data structure for the maintenance of these orders such that an update can be performed in time O(log n). The discovered structural properties of planar st-graphs provide a unifying theoretical underpinning for several applications, such as dynamic point location in planar monotone subdivisions, dynamic transitive-closure query in planar st-graphs, and dynamic contact-chain query in convex subdivisions. The presented techniques significantly outperform previously known solutions of the same problems.
展开▼
