On-Line Planarity Testing

1996/10/01 by Giuseppe Di Battista, Roberto Tamassia · 241 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Optimization and Search Problems #Software Testing and Debugging Techniques #Planarity testing #Combinatorics #Vertex (graph theory) #Mathematics #Planar graph #Wheel graph #Planar #Book embedding #Graph #Line graph #Discrete mathematics #Computer science #Graph power #Pathwidth

paper · doi:10.1137/s0097539794280736

published in SIAM Journal on Computing 25(5), 956-997 (Society for Industrial and Applied Mathematics)

openalex publication_date 1996/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11

Abstract

The on-line planarity-testing problem consists of performing the following operations on a planar graph G: (i) testing if a new edge can be added to G so that the resulting graph is itself planar; (ii) adding vertices and edges such that planarity is preserved. An efficient technique for on-line planarity testing of a graph is presented that uses O(n) space and supports tests and insertions of vertices and edges in O(log n) time, where n is the current number of vertices of G. The bounds for tests and vertex insertions are worst-case and the bound for edge insertions is amortized. We also present other applications of this technique to dynamic algorithms for planar graphs.

Citations

• On-line graph algorithms with SPQR-trees
• A linear algorithm for embedding planar graphs using PQ-trees
• Efficient Planarity Testing
• Dividing a Graph into Triconnected Components
• Algorithms for plane representations of acyclic digraphs
• Maintaining bridge-connected and biconnected components on-line
• Fast Algorithms for Finding Nearest Common Ancestors
• A data structure for dynamic trees
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On the Complexity of Covering Vertices by Faces in a Planar Graph
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Small sets supporting fary embeddings of planar graphs
• Non-separable and planar graphs

Cited by

• On-line maintenance of triconnected components with SPQR-trees
• On-line Planar Graph Embedding
• Extending Steinitz’s Theorem to Upward Star-Shaped Polyhedra and Spherical Polyhedra
• SPQR tree [wikipedia]