SpecializedSource checked

Articulation Point Detection

Finds graph nodes whose removal would split a connected graph.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Graph Traversal
Difficulty: Advanced
Family: Connectivity Analysis
Tier: Specialized
Status: Verified
Review: Source Checked
Sources: 3
Formulas: 0
Relationships: 1
Code example: Not ready
Visualization: Ready
Aliases: Cut Vertex Detection

Overview

Articulation Point Detection uses DFS discovery times and low-link values to identify critical connector nodes.

Core Concepts

graph representationconnected componenttraversal orderconnectivity analysisvisited setfrontier expansion

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(V + E)

Average

O(V + E)

Worst

O(V + E)

Space

O(V)

When to Use

Use Articulation Point Detection when you need to compute low-link values in an undirected graph.
Use it for network reliability with inputs like undirected graph.
Use it when relationships are naturally modeled as nodes connected by edges.
Use it when the Connectivity Analysis tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when the graph is so large that storing every visited node is not practical.
Avoid it when the required output is not articulation point list.

What It Does

Computes low-link values in an undirected graph
Marks nodes that separate child subtrees

Use Cases

Network reliability
Infrastructure analysis
Graph vulnerability checks

Inputs

Undirected graph

Outputs

Articulation point list

Pseudocode

1.Run DFS and assign discovery times
2.Compute low-link values for each subtree
3.Mark a root with multiple DFS children
4.Mark a non-root when a child cannot reach an ancestor
5.Return all marked nodes

Canonical Example

Input: graph = {A: [B, C], B: [D], C: [], D: []}, start = A
Output: visited = [A, B, C, D]
Explanation: Articulation Point Detection: The traversal starts at A and visits reachable nodes by following edges.

Implementation Notes

Keep the input contract explicit: Undirected graph.
Use this step as the implementation spine: Run DFS and assign discovery times.
Then preserve the next state change: Compute low-link values for each subtree.
Keep node ids, edge direction, and visited state explicit in the implementation.
Represent neighbors consistently and keep traversal state separate from the graph data.

Common Pitfalls

The root node uses a special rule based on its number of DFS children.
Not defining directed versus undirected edges clearly can change the result.
Forgetting to mark visited nodes before revisiting cycles or shared neighbors.
Returning articulation point list without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show connector nodes whose removal separates graph regions.

Step 1 of 5: Run DFS and assign discovery times

critical-node

Notes

Articulation Point Detection operates in O(V + E) time and O(V) space within the Connectivity Analysis family. Often compared with Depth-First Search and Connected Components.