Algorithmic Solutions > LEDA > LEDA Guide > Graph Algorithms > Basic Graph Algorithms > Biconnected Components

Biconnected Components

What are Biconnected Components of a Graph?

An undirected graph is called biconnected if for every pair of nodes u and v there are two node disjoint paths between u and v. To disconnect a biconnected graph you need to delete at least two nodes. The biconnected components of an undirected graph are its maximal biconnected subgraphs.

What are Biconnected Components good for?

Some graph algorithms only work for biconnected graphs. One method to apply such an algorithm to a graph that is not biconnected is to compute the biconnected components and apply the algorithm to each component separately.

Example of how to compute biconnected components

Running Time

The running time is linear in the size of the graph (O(|V|+|E|)).

See also:

Basic Graph Algorithms

Graphs and Related Data Types

GraphWin for visualizing graphs and graph algorithms


Manual Entries:

Manual Page Basic Graph Algorithms




Please send any suggestions, comments or questions to leda@algorithmic-solutions.com
© Copyright 2001-2003, Algorithmic Solutions Software GmbH