Maintenance of 2- and 3-edge-connected components of graphs. I (Q685694)

This paper deals with dynamic maintenance of 2- and 3-edge-connected components of a graph under insertions of edges. Before we define the objects above, let us recall that a dynamic graph algorithm is an algorithm which maintains some information (e.g. a minimum spanning tree) while the graph is being changed (e.g. by inserting or deleting an edge). The idea is to exploit a suitable data structure to allow for a faster updating procedure than the obvious one where one just recalculates from scratch. To do so often requires quite a bit of ingenuity, even for very simple problems such as the minimum spanning tree problem. Let \(G=(V,E)\) be an undirected graph. Two vertices \(x,y \in V\) are said to be \(k\)-edge-connected if after removal of any set of at most \(k-1\) edges from \(G\), there is still a path between \(x\) and \(y\). By Menger's theorem this is equivalent to saying that there exist \(k\)-edge-disjoint paths between \(x\) and \(y\). It is an easy exercise to prove that \(k\)-edge- connectivity is an equivalence relation on \(V\). A 2-edge-connected component of \(G\) is a subgraph \(H\) induced by some equivalence class under the relation of 2-edge-connectivity. It is easy to show that if \(x,y \in V(H)\) are \(k\)-edge-connected in \(G\), then they are also \(k\)- edge-connected in \(H\). If we define a 3-edge-connected component in a similar way, then the last observation does not hold. Hence the authors define a 3-edge-connected component as an equivalence class \(H\) under the relation of 3-edge-connectivity extended with some additional (new) edges so that \(x,y\in H\) are \(k\)-edge-connected in \(G\) if and only if they are \(k\)-edge-connected in \(H\). The authors provide a data structure which allows efficient maintainance of the 2- and 3-edge-connected components of a given graph \(G\). Starting from a graph on \(n\) vertices and no edges, the insertion of \(e\) edges takes \(O(n\log n+e)\) time. The data structure allows for insertions of vertices also (in the same time bounds, taking \(n\) as the final numbers of vertices). Moreover, at any moment, the data structure can answer the following type of query in \(O(1)\) time: given two vertices in the actual graph, are these two vertices 2- or 3-edge-connected.