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
Use Cases
Frequently Asked Questions
From the Blog
What Is K-Means Clustering Explained
K-means clustering groups unlabeled data into k clusters by repeatedly assigning points to the nearest center and moving centers to the middle of their points.
Read More Career GrowthData Analyst Resume: A Template That Gets Interviews
Build a data analyst resume that gets interviews with a proven structure, the right keywords, quantified bullet points, and projects that prove your skills.
Read More AI & TechnologyWhat Is a Line Graph and When Should You Use One?
A line graph plots data points connected by straight lines to show how a value changes over a continuous scale, usually time. This guide explains how to read one, when it's the right chart choice, and common mistakes to avoid.
Read More AI & TechnologyHow to Use ChatGPT to Improve Your Resume
ChatGPT can rewrite bullet points, tighten wording, and tailor a resume to a specific job description, but it works best as an editor rather than the original author of your experience. This guide covers effective prompts and common pitfalls to avoid.
Read More