Certificates and fast algorithms for biconnectivity in fully dynamic graphs

In this paper, we present sparse certificates for biconnectivity together with algorithms for updating these certificates. We thus obtain fully-dynamic algorithms for biconnectivityin graphs that run in O ( √ n log n log ⌈ m ⌉) amor-n tized time per operation, where m is the number of edges and n is the number of nodes in the graph. This improves upon the results in [12], in which algorithms were presented running in O ( √ m log n) amortized time, and solves the open problem to find certificates to speed up biconnectivity, as stated in [2].