Checking the biconnectivity of a biconnected graph with a vertex removed

Question

If I have a biconnected graph and I remove a vertex (without forgetting which vertex was removed and which vertices it was adjacent to), is there an way to check the biconnectivity of the resulting graph that is easier than checking the biconnectivity of an arbitrary graph? E.g., is there a method that in the best case requires only local examination (perhaps some property of the adjacent vertices)?

Answer 1

What you're looking for is 3-connectivity checking (if you remove any vertex from a 3-connected graph it produces another 3-connected or a biconnected graph. It kind of works like bi-connectivity and simple connectivity, in fact you can generalize this principal to k-connectivity).

An efficient method (linear time) to check 3-connectivity can be derived from the Tarjan-Hopcroft algorithm. This method splits a 2-connected graph into a 3-conncted multigraph. If the algorithm doesn't split the graph it means that the graph is already 3-connected.

However I have to warn you, the literature around this algorithm is quite complicated and is not the best one to start learning about graph analysis algorithms.