Fully Dynamic Planarity Testing in Planar Embedded Graphs (Extended Abstract)
Lists
Only you see this
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...