Paper Info
Title
Fully Dynamic Planarity Testing in Planar Embedded Graphs (Extended Abstract)
Abstract
We present the first data structure to maintain an embedded planar graph under arbitrary edge insertions, arbitrary edge deletions and queries that test whether the insertion of a new edge would violate the planarity of the embedding. Our data structure supports online updates and queries on an n-vertex embedded planar graph in O(log2 n) worst-case time, it can be built in linear time and requires linear storage.
Year
DOI
Venue
1993
10.1007/3-540-57273-2_57
ESA
Keywords
Field
DocType
extended abstract,dynamic planarity testing,data structure,linear time,planar graph
Topology,Discrete mathematics,Outerplanar graph,Combinatorics,Planarity testing,Computer science,Planar straight-line graph,Book embedding,Pathwidth,Topological graph theory,1-planar graph,Planar graph
Conference
ISBN
Citations 
PageRank 
3-540-57273-2
7
0.51
References 
Authors
10
3
Name
Order
Citations
PageRank
Giuseppe F. Italiano12364254.07
Johannes A. La Poutré230824.78
Monika Rauch Henzinger34307481.86