Maintenance of 2-and 3-edge-connected components of graphs II

Data structures and algorithms are presented to efficiently maintain the 2- and 3-edge-connected components of general graph, under insertions of edge s and nodes in the graph. At any moment, the data structure can answer whet her two nodes are 2- or 3-edge-connected. The algorithms run in O(n+m.alpha (m, n)) time, where m is the total number of queries and edge insertions. F urthermore, linear-time algorithm is presented for maintaining the 2-edge-c onnected components in case the initial graph is connected. Finally, new so lution is presented for the 2-vertex-connected components of graph.