Decremental 2- and 3-connectivity on planar graphs

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