6533b7d0fe1ef96bd125a2bd

RESEARCH PRODUCT

Dynamic 2- and 3-connectivity on planar graphs

Dora GiammarresiGiuseppe F. Italiano

subject

Amortized analysisBook embeddingPlanar straight-line graph1-planar graphPlanar graphCombinatoricssymbols.namesakePathwidthChordal graphTheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITYOuterplanar graphData_FILESsymbolsMathematicsofComputing_DISCRETEMATHEMATICSMathematics

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 of O(n log n) time under any sequence of at most O(n) deletions. This gives O(log n) amortized time per deletion. The 2-vertex- and 3-edge-connected components can be maintained in a total of O(n log2n) time. This gives O(log2n) amortized time per deletion. The space required by all our data structures is O(n).

yearjournalcountryeditionlanguage
1992-01-01
https://doi.org/10.1007/3-540-55706-7_19