Articulation Points
Graph connectivity analysis technique
An articulation point (or cut vertex) is a vertex in an undirected graph whose removal increases the number of connected components, meaning the vertex is critical to keeping part of the graph connected.
Definition
An articulation point (or cut vertex) is a vertex in an undirected graph whose removal increases the number of connected components, meaning the vertex is critical to keeping part of the graph connected.
Overview
In network and graph analysis, articulation points identify structural weak spots: single points of failure whose removal splits a connected graph into two or more disconnected pieces. A graph with no articulation points is called biconnected, meaning it remains connected even after removing any single vertex, which is a desirable robustness property for networks such as power grids, communication infrastructure, or road systems. Articulation points are found using a depth-first search that tracks two values for each vertex: its discovery time (the order in which DFS first visits it) and its low-link value (the earliest discovery time reachable from that vertex's subtree, including through at most one back edge). A non-root vertex u is an articulation point if it has a child v in the DFS tree such that no vertex in v's subtree has a back edge to an ancestor of u strictly earlier than u itself; the root of the DFS tree is an articulation point if it has more than one child in the DFS tree. This algorithm, due to Hopcroft and Tarjan, runs in O(V + E) time using a single DFS traversal. Articulation points are a core tool in network reliability and infrastructure planning: identifying them highlights routers, servers, bridges, or intersections whose failure would fragment a network, informing where redundancy should be added. They are closely related to bridges (critical edges rather than critical vertices) and to biconnected components, the maximal subgraphs that remain connected after removing any single vertex, which partition a graph's edges around its articulation points.
Key Concepts
- Identifies vertices whose removal disconnects part of a graph
- Computed via a single depth-first search tracking discovery and low-link values
- Based on the Hopcroft-Tarjan algorithm, running in O(V + E) time
- Root of the DFS tree is an articulation point if it has more than one child
- Non-root vertices identified via low-link comparisons with ancestors
- A graph with no articulation points is called biconnected
- Closely related to bridges (critical edges) in the same graph
- Used to define biconnected components partitioning the graph's edges