ISSN:
1432-0541
Keywords:
Planarst-graph
;
Transitive closure
;
Point location
;
Contact-chain
;
Planar subdivision
;
Dynamic data structure
;
On-line algorithm
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We show that a planarst-graphG admits two total orders on the setV∪E ∪F, whereV, E, andF are respectively the set of vertices, edges, and faces ofG, with ¦V¦ =n. Assuming thatG is to be dynamically modified by means of insertions of edges and expansions of vertices (and their inverses), we exhibit anO(n)-space dynamic data structure for the maintenance of these orders such that an update can be performed in timeO(logn). The discovered structural properties of planarst-graphs provide a unifying theoretical underpinning for several applications, such as dynamic point location in planar monotone subdivisions, dynamic transitive-closure query in planarst-graphs, and dynamic contact-chain query in convex subdivisions. The presented techniques significantly outperform previously known solutions of the same problems.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01840401
Permalink