Fully Dynamic Planarity Testing in Planar Embedded Graphs (Extended Abstract)

Giuseppe F. Italiano, Johannes A. La Poutré, Monika RauchESA 1993 · OpenReview

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.
BibTeX
@inproceedings{italiano1993fully,
  author = {Giuseppe F. Italiano and Johannes A. La Poutré and Monika Rauch},
  title = {{Fully Dynamic Planarity Testing in Planar Embedded Graphs (Extended Abstract)}},
  booktitle = {ESA},
  year = {1993},
  url = {https://openreview.net/forum?id=XXStQlO93},
}

Loading related content...

Figure