On-line graph algorithms with SPQR-trees

1990/01/01 by Giuseppe Di Battista, Roberto Tamassia · 43 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Biconnected graph #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Data Management and Algorithms #Data structure #Graph #Line graph #Mathematics #Pathwidth #Planarity testing #Spanning tree #Theoretical computer science #Transitive closure #Tree decomposition #Voltage graph

paper · doi:10.1007/bfb0032061

published in Lecture Notes in Computer Science, 598-611 (Springer Berlin Heidelberg)

crossref issued 1990/01/01 · crossref published 1990/01/01 · crossref published-print 1990/01/01 · openalex publication_date 1990/01/01 · crossref published-online 2005/06/27 · crossref created 2005/12/11 · crossref deposited 2020/04/11 · openalex created_date 2025/10/10 · crossref indexed 2025/10/14 · openalex updated_date 2026/07/31

Citations

• Algorithms for plane representations of acyclic digraphs
• A data structure for dynamic trees
• A linear-time algorithm for a special case of disjoint set union

Cited by

• A Linear Time Implementation of SPQR-Trees
• On-Line Planarity Testing
• On-line Planar Graph Embedding
• Alpha-algorithms for incremental planarity testing (preliminary version)
• Fully dynamic planarity testing with applications
• SPQR tree [wikipedia]