(

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.

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.