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)?
Checking the biconnectivity of a biconnected graph with a vertex removed
3
$\begingroup$
graph-theory
-
0That shortcut you mentioned is exactly the sort of thing I'm after. I do realize that no algorithm could be local in the worst case. – 2011-03-22