6533b862fe1ef96bd12c7742

RESEARCH PRODUCT

Decremental 2- and 3-connectivity on planar graphs

Giuseppe F. ItalianoDora Giammarresi

subject

Vertex (graph theory)Discrete mathematicsDynamic data structuresAmortized analysisGeneral Computer ScienceApplied MathematicsVertex connectivityPlanar graphsData structureEdge connectivityComputer Science ApplicationsPlanar graphCombinatoricssymbols.namesakeAnalysis of algorithms Dynamic data structures Edge connectivity Planar graphs Vertex connectivitysymbolsAnalysis of algorithmsVertex connectivityDynamic data structuresAnalysis of algorithmsMathematics

description

We study the problem of maintaining the 2-edge-, 2-vertex-, and 3-edge-connected components of a dynamic planar graph subject to edge deletions. The 2-edge-connected components can be maintained in a total ofO(n logn) time under any sequence of at mostO(n) deletions. This givesO(logn) amortized time per deletion. The 2-vertex- and 3-edge-connected components can be maintained in a total ofO(n log2n) time. This givesO(log2n) amortized time per deletion. The space required by all our data structures isO(n). All our time bounds improve previous bounds.

yearjournalcountryeditionlanguage
1996-09-01Algorithmica
https://doi.org/10.1007/bf01955676