On-line maintenance of triconnected components with SPQR-trees

1996/04/01 by G. Di Battista, Giuseppe Di Battista, R. Tamassia +1 · 89 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Ackermann function #Algorithms and Data Compression #Biconnected graph #Combinatorics #Computer science #DNA and Biological Computing #Disjoint sets #Geometry #Graph #Inverse #Line graph #Mathematics #Tree (set theory) #VLSI and Analog Circuit Testing #Vertex (graph theory)

paper · doi:10.1007/bf01961541

published in Algorithmica 15(4), 302-318 (Springer Science and Business Media LLC)

crossref issued 1996/04/01 · crossref published 1996/04/01 · crossref published-print 1996/04/01 · openalex publication_date 1996/04/01 · crossref created 2005/07/29 · crossref deposited 2020/04/08 · openalex created_date 2025/10/10 · crossref indexed 2026/04/10 · openalex updated_date 2026/07/31

Citations

• Dividing a Graph into Triconnected Components
• Incremental planarity testing
• Maintaining bridge-connected and biconnected components on-line
• A linear-time algorithm for a special case of disjoint set union
• On-Line Planarity Testing
• On-line Planar Graph Embedding

Cited by

• Fully-dynamic planarity testing in polylogarithmic time
• Extending Steinitz’s Theorem to Upward Star-Shaped Polyhedra and Spherical Polyhedra
• Planarity testing [wikipedia]