On-line maintenance of the four-connected components of a graph

Given a graph G with n vertices and m edges, a k-connectivity query for vertices v and v of G asks whether there exist k disjoint paths between v and v. The authors consider the problem of performing k-connectivity queries for k 4. First, they present a static data structure that answers such queries in O(1) time. Next, they consider the problem of performing queries intermixed with online updates that insert vertices and edges. For triconnected graphs they give a dynamic data structure that supports queries and updates in time O((l, n)) amortized, where n is the current number of vertices of the graph and l is the total number of operations performed ((l, n) denotes the slowly growing Ackermann's function inverse). For general graphs, a sequence of l operations takes total time O(n log n + l). All of the above data structures use space O(n), proportional to the number of vertices of the graph. The results also yield an efficient algorithm for testing whether graph G is four-connected that runs in O(n(n, n) + m) time using O(n + m) space.

On-line maintenance of the four-connected components of a graph Conference Paper