(graph theory, algorithms:)
A component of a graph (undirected!) given by a stronger connectivity than plain connected components.

Definition

Given a graph G, define an equivalence relation on the edges: we say e~f iff edges e,f are on some simple cycle. The biconnected components of G are the equivalence classes of G/~. Naturally, every biconnected component is connected, but biconnected components may split connected components.

The same vertex of the graph may participate in multiple biconnected components -- see articulation point.

Example:

The biconnected components of the following (connected!) graph:
*--*  *--*
|\/  /|
|/\ / |
*--*--*
are these:
*--*      *   *--*
|\/      /|
|/\     / |
*--*   *--*
Note the duplication of the articulation points in the above diagrams.

Algorithmic considerations

An online algorithm for dealing with connected components is Tarjan's union find with path compression. Tarjan also has another (more complex) algorithm, which does the same for biconnected components, and has the same amortized time complexity. This second algorithm uses union find with path compression as a subroutine.

Log in or register to write something here or to contact authors.