On-line graph algorithms with SPQR-trees

DOI10.1007/BFB0032061MaRDI QIDQ4038721zbMATH OpenFDO

Authors Giuseppe Di Battista, Roberto Tamassia

Publication date 18 May 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0032061

zbMATH Keywords

on-line graph problemSPQR-tree

Mathematics Subject Classification ID

Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On-line maintenance of triconnected components with SPQR-trees
• scientific article; zbMATH DE number 2080088
• scientific article; zbMATH DE number 2038697
• Using SPQR-trees to speed up algorithms based on 2-cutset decompositions
• scientific article; zbMATH DE number 4168710

Cited in

(36)

• Maintaining bridge-connected and biconnected components on-line
• On counting planar embeddings
• 3-connected reduction for regular graph covers
• Using SPQR-trees to speed up recognition algorithms based on 2-cutsets
• Upward planarity testing
• On-line maintenance of triconnected components with SPQR-trees
• Decremental 2- and 3-connectivity on planar graphs
• An SPQR-tree-like embedding representation for upward planarity
• Online graph exploration on trees, unicyclic graphs and cactus graphs
• Jordan-like characterization of automorphism groups of planar graphs
• Planar embeddings with small and uniform faces
• Average case analysis of fully dynamic reachability for directed graphs
• Using SPQR-trees to speed up algorithms based on 2-cutset decompositions
• scientific article; zbMATH DE number 2038697 (Why is no real title available?)
• scientific article; zbMATH DE number 2080088 (Why is no real title available?)
• Planar L-drawings of directed graphs
• A Möbius-invariant power diagram and its applications to soap bubbles and planar Lombardi drawing
• Dynamic 2- and 3-connectivity on planar graphs
• A linear algorithm for the maximal planar subgraph problem
• Computing k-modal embeddings of planar digraphs
• Approximation Algorithms for Facial Cycles in Planar Embeddings
• Fast incremental planarity testing
• Maintenance of triconnected components of graphs
• Graph isomorphism restricted by lists
• scientific article; zbMATH DE number 7765366 (Why is no real title available?)
• The Rique-number of graphs
• Output-sensitive reporting of disjoint paths (extended abstract)
• On-line convex planarity testing
• Average case analysis of fully dynamic connectivity for directed graphs
• Undirected vertex-connectivity structure and smallest four-vertex-connectivity augmentation (extended abstract)
• Enumerating combinatorial resultant trees
• Extending partial representations of circle graphs in near-linear time
• Dynamic algorithms for shortest paths in planar graphs
• Dynamic reachability in planar digraphs with one source and one sink
• Dynamic embeddings of dynamic single-source upward planar graphs
• Connectivity of workflow nets: The foundations of stepwise verification

This page was built for publication: On-line graph algorithms with SPQR-trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4038721)