Decremental Biconnectivity on Planar Graphs

W.-B. Strothmann, T. Lukovszki, Decremental Biconnectivity on Planar Graphs, Paderborn, 1997.

Download
Restricted pub-hni-901.pdf 222.11 KB
Report | English
Author
;
Abstract
In this paper we present a (randomized) algorithm for maintaining the biconnected components of a dynamic planar graph of $n$ vertices under deletions of edges. The biconnected components can be maintained under any sequence of edge deletions in a total of $O(n log n)$ time, with high probability. This gives $O(log n)$ amortized time per edge deletion, which improves previous (deterministic) results due to Giammarresi and Italiano, where $O(n log^2 n)$ amortized time is needed. Our work describes a simplification of the data structures from [GiIt96] and uses dynamic perfect hashing to reduce the running time. As in the paper by Giammarresi and Italiano, we only need $O(n)$ space. Finally we describe some simply additional operations on the decremental data structure. By aid of them this the data structure is applicable for finding efficiently a $Delta$-spanning tree in a biconnected planar graph with a maximum degree $2Delta-2$ do to Czumaj and Strothmann.
Publishing Year
LibreCat-ID

Cite this

Strothmann W-B, Lukovszki T. Decremental Biconnectivity on Planar Graphs. Paderborn; 1997.
Strothmann, W.-B., & Lukovszki, T. (1997). Decremental Biconnectivity on Planar Graphs. Paderborn.
@book{Strothmann_Lukovszki_1997, place={Paderborn}, title={Decremental Biconnectivity on Planar Graphs}, author={Strothmann, Willy-Bernhard and Lukovszki, Tamás}, year={1997} }
Strothmann, Willy-Bernhard, and Tamás Lukovszki. Decremental Biconnectivity on Planar Graphs. Paderborn, 1997.
W.-B. Strothmann and T. Lukovszki, Decremental Biconnectivity on Planar Graphs. Paderborn, 1997.
Strothmann, Willy-Bernhard, and Tamás Lukovszki. Decremental Biconnectivity on Planar Graphs. 1997.
Main File(s)
File Name
pub-hni-901.pdf 222.11 KB
Access Level
Restricted Closed Access
Last Uploaded
2020-09-03T12:59:44Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar