Explanation of Algorithm for finding articulation points or cut vertices of a graph

Question

I have searched the net and could not find any explanation of a DFS algorithm for finding all articulation vertices of a graph. There is not even a wiki page.

From reading around, I got to know the basic facts from here. PDF

There is a variable at each node which is actually looking at back edges and finding the closest and upmost node towards the root node. After processing all edges it would be found.

But I do not understand how to find this down & up variable at each node during the execution of DFS. What is this variable doing exactly?

Please explain the algorithm.

Thanks.

Answer 1

Finding articulation vertices is an application of DFS.

In a nutshell,

1. Apply DFS on a graph. Get the DFS tree.
2. A node which is visited earlier is a "parent" of those nodes which are reached by it and visited later.
3. If any child of a node does not have a path to any of the ancestors of its parent, it means that removing this node would make this child disjoint from the graph.
4. There is an exception: the root of the tree. If it has more than one child, then it is an articulation point, otherwise not.

Point 3 essentially means that this node is an articulation point.

Now for a child, this path to the ancestors of the node would be through a back-edge from it or from any of its children.

All this is explained beautifully in this PDF.