Decremental 2- and 3-connectivity on planar graphs

DOI10.1007/BF01955676zbMath0858.68064OpenAlexW1991632262MaRDI QIDQ1924402

Dora Giammarresi, Giuseppe F. Italiano

Publication date: 16 October 1996

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

planar graphsanalysis of algorithmsvertex connectivitydynamic data structuresedge connectivity

Mathematics Subject Classification ID

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

Related Items (3)

Optimal decremental connectivity in planar graphs ⋮ Decremental SPQR-trees for Planar Graphs ⋮ Contracting a Planar Graph Efficiently

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maintenance of 2- and 3-edge-connected components of graphs. I
• Maintaining bridge-connected and biconnected components on-line
• Improved data structures for fully dynamic biconnectivity
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• An On-Line Edge-Deletion Problem
• Maintenance of a minimum spanning forest in a dynamic plane graph
• Fully Dynamic Algorithms for 2-Edge Connectivity
• Maintaining the 3-Edge-Connected Components of a Graph On-Line

This page was built for publication: Decremental 2- and 3-connectivity on planar graphs