Articulation Point and Bridge

The choking points of a graph By Yihang Ho

I was explaining the idea of articulation point and bridge to someone who has never heard of graph theory. That was a little challenging, but fun at the same time.

Imagine that you run an airline, and your planes fly between a selected set of airports. This scenario actually can be described by a graph - each airport is a node and each flight between two airports is an edge. We call a graph connected if, using our airline analogy, a passenger can start from any airport of her choice, and arrive at any other airport after some finite transits.

Suppose that one of these airports is forced to shutdown due to a natural disaster. Let's call this airport X. Clearly, your passengers will not be able to arrive at airport X. However, it is possible that some of the other airports become inaccessible as your passengers need to transit at X to arrive at these airports. For example, our airline flies between, A and X, and X and B. If X is shut down, then passenger from A will not be able to arrive at B and vice versa. Airports like X that break the connectivity of the entire graph when removed are called the articulation points.

Now, instead of shutting down an airport, one of the many flights becomes unavailable - our airline decided not to fly between X and Y anymore. Again, some of the destinations might become inaccessible. As an example, our airline initially flies between A and X, X and Y, and Y and B. If we stop flying between X and Y, passengers from A will not be able to arrive at B and vice versa. Flights like X-Y that break the connectivity when removed are called bridges.

The algorithm for finding articulation points and bridges is simple. One naïve way is to remove each possible node and edge, and check if the graph is still connected. This requires V+E DFSes. A better solution can solve this problem with a single DFS, proposed by John Hopcroft and Robert Endre Tarjan. This solution is readily available on the internet. One thing that is possibly confusing about this algorithm is:

The root vertex is an articulation point if and only if it has more than 2 children.

This statement refers to the graph formed by DFS, not the original graph itself.