Skip to main content

Biconnected Components

Description​

Biconnected components are parts of the graph important in the initial analysis. Finding biconnected components means finding a maximal biconnected subgraph. Subgraph is biconnected if:

  • It is possible to go from each node to another within a biconnected subgraph
  • The first scenario remains true even after removing any vertex in the subgraph

The problem was solved by John Hopcroft and Robert Tarjan with linear time complexity. Depending on the use case, biconnected components may help to discover hidden structures within the graph.

drawing

Different colors are different components. Multi-colored vertices are articulation points.

Materials​

Implementation​

Biconnected Components

Biconnected Components

Biconnected Components is implemented as part of the MAGE project. Be sure to check it out in the link above. ☝️

Use cases​

Biconnected components detection is a base for many graph analytics algorithms. Therefore, it is rarely used alone. However, there are particular niche use cases where finding biconnected components might come in handy mostly because of the articulation points revealing.

Transportation

Organizing the road infrastructure can be a painful task for any engineer. Finding biconnected components in the transportation network can help to reveal different zones in an urban area. Furthermore, the goal would be enlarging such zones and having as few articulation points as possible, since these are the places where there is the highest possibility of traffic congestion.