Overview
Biconnected-component decomposition uses depth-first search discovery times and lowlink values to group edges into blocks separated by articulation points.
CoreSource checked
Biconnected Components
Finds maximal graph regions that stay connected after removing any one vertex.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Graph Traversal
- Difficulty
- Intermediate
- Family
- Graph Connectivity
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 2
- Code example
- Ready
- Visualization
- Ready
Core Concepts
biconnected component decompositiongraph connectivitydepth-first searchlowlink valuesgraph traversal
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(V + E)
Average
O((V + E) log V)
Worst
O(V^2 + E)
Space
O(V + E)
When to Use
- Use when undirected graph robustness around articulation points matters.
- Use when edge blocks, not only articulation vertices, are needed.
When Not to Use
- Avoid when the graph is directed unless using a directed analogue.
- Avoid when simple connected components answer the question.
What It Does
- Runs DFS while tracking discovery and lowlink values
- Identifies articulation points that separate blocks
- Groups edges into maximal biconnected components
Use Cases
- Network vulnerability analysis
- Graph decomposition before block-cut tree construction
- Finding articulation-separated regions
Inputs
- Directed flowgraph G = (V, E, r) rooted at entry vertex r
Outputs
- Immediate dominator tree idom[v] for every reachable vertex
Pseudocode
- 1.For each unvisited vertex, start DFS
- 2.Assign discovery time and lowlink
- 3.Push traversed tree and back edges onto a stack
- 4.After visiting a child, update lowlink
- 5.When child lowlink reaches the parent discovery time, pop one component
- 6.Return all biconnected components and articulation points
Canonical Example
- Input
- triangles A-B-C-A and C-D-E-C sharing only vertex C
- Output
- two biconnected components separated at articulation vertex C
- Explanation
- Removing C disconnects the two triangle blocks, while each triangle remains internally biconnected.
Implementation Notes
- Track parent, discovery time, lowlink, and an edge stack.
- Start DFS from every unvisited vertex.
- Test a triangle with a single bridge to another triangle.
Common Pitfalls
- Treating the DFS root like other articulation points without checking child count.
- Forgetting to push and pop edges for each component.
- Mishandling parallel edges or disconnected components.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow using DFS lowlink values to identify articulation-separated components on a small biconnected component decomposition example.
Step 1 of 6: For each unvisited vertex, start DFS
graph-traversal-mechanismNotes
The algorithm is for undirected graphs; directed strong connectivity is a different problem.
Sources (1)
What each reference supports for this entry.
Depth-First Search and Linear Graph Algorithms
PaperClassic reference for DFS low-link reasoning and biconnected-component decomposition.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageDFS discovery and lowlink values drive the decomposition.
Conceptual neighborBridge Detection
Both use lowlink values to find graph separation structure.
Related Algorithms
Tags
GraphTraversal