Dynamic Maintenance of Planar Digraphs, with Applications
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1988
- Accession Number
- ADA197051
Entities
People
- Franco Preparata
- Roberto Tamassia
Organizations
- University of Illinois Urbana–Champaign