Incremental planarity testing
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 436-441
- https://doi.org/10.1109/sfcs.1989.63515
Abstract
The incremental planarity testing problem consists of performing the following operations on a planar graph G with n vertices: (1) testing whether a new edge can be added to G so that the resulting graph is itself planar; (2) adding vertices and edges such that planarity is preserved. An efficient technique for incremental planarity testing that uses O(n) space and supports tests and insertion of vertices and edges in O(log n) time is presented. The bounds for queries and vertex insertions are worst case, and the bound for edge insertions is amortized.Keywords
This publication has 13 references indexed in Scilit:
- Dynamic maintenance of planar digraphs, with applicationsAlgorithmica, 1990
- On Finding Lowest Common Ancestors: Simplification and ParallelizationSIAM Journal on Computing, 1988
- Fully dynamic techniques for point location and transitive closure in planar structuresPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- A unified approach to visibility representations of planar graphsDiscrete & Computational Geometry, 1986
- Fast Algorithms for Finding Nearest Common AncestorsSIAM Journal on Computing, 1984
- A data structure for dynamic treesJournal of Computer and System Sciences, 1983
- An efficient heuristic for identifying a maximum weight planar subgraphPublished by Springer Nature ,1982
- A graph-planarization algorithm and its application to random graphsPublished by Springer Nature ,1981
- Computing an st-numberingTheoretical Computer Science, 1976
- Efficient Planarity TestingJournal of the ACM, 1974