Incremental planarity testing

1989/01/01 by Giuseppe Di Battista, Roberto Tamassia · 134 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Optimization and Search Problems #Software Testing and Debugging Techniques #Planarity testing #Combinatorics #Vertex (graph theory) #Graph #Computer science #Enhanced Data Rates for GSM Evolution #Planar graph #Mathematics #Artificial intelligence

paper · doi:10.1109/sfcs.1989.63515

openalex publication_date 1989/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

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.>

Citations

• Efficient Planarity Testing
• Dividing a Graph into Triconnected Components
• Algorithms for plane representations of acyclic digraphs
• Fast Algorithms for Finding Nearest Common Ancestors
• A data structure for dynamic trees
• On the Complexity of Covering Vertices by Faces in a Planar Graph
• On Finding Lowest Common Ancestors: Simplification and Parallelization

Cited by

• On-line maintenance of triconnected components with SPQR-trees
• On-line Planar Graph Embedding
• Alpha-algorithms for incremental planarity testing (preliminary version)
• Fully dynamic planarity testing with applications
• SPQR tree [wikipedia]