An Articulation Point, also called a Cut Vertex, is a vertex in an undirected graph whose removal increases the number of connected components.

In practical terms, it is a structural single point of failure.

If the vertex disappears, parts of the graph that were previously connected may become separated.

Example

A -- B -- C
     |
     D

Removing B disconnects the remaining vertices.

Therefore:

B = articulation point

Articulation Point vs Bridge

An articulation point is a critical vertex.

A bridge is a critical edge.

Articulation Point → remove vertex
Bridge             → remove edge

Brute-force approach

A simple approach removes each vertex one at a time and recomputes connected components.

Its cost can reach:

O(V × (V + E))

A DFS-based Tarjan method finds all articulation points in linear time.

Discovery and low-link values

For each vertex u:

disc[u]

is the time when DFS first discovers it.

low[u]

is the earliest discovery time reachable from u's DFS subtree through tree edges and a back edge.

Low-link values tell us whether a subtree has an alternate route to an ancestor.

Non-root condition

For a DFS tree edge:

u → v

if u is not the root and:

low[v] >= disc[u]

then u is an articulation point.

The subtree rooted at v cannot reach an ancestor above u without passing through u.

Root condition

The DFS root follows a separate rule.

It is an articulation point when it has more than one DFS child:

children > 1

JavaScript implementation

function findArticulationPoints(graph) {
  const nodes = new Set();

  for (const [u, neighbors] of Object.entries(graph)) {
    nodes.add(u);

    for (const v of neighbors) {
      nodes.add(v);
    }
  }

  const visited = new Set();
  const disc = new Map();
  const low = new Map();
  const parent = new Map();
  const articulation = new Set();

  let time = 0;

  function dfs(u) {
    visited.add(u);

    disc.set(u, ++time);
    low.set(u, disc.get(u));

    let children = 0;

    for (const v of graph[u] ?? []) {
      if (!visited.has(v)) {
        children++;
        parent.set(v, u);

        dfs(v);

        low.set(
          u,
          Math.min(low.get(u), low.get(v))
        );

        const isRoot = !parent.has(u);

        if (isRoot && children > 1) {
          articulation.add(u);
        }

        if (
          !isRoot &&
          low.get(v) >= disc.get(u)
        ) {
          articulation.add(u);
        }
      } else if (v !== parent.get(u)) {
        low.set(
          u,
          Math.min(low.get(u), disc.get(v))
        );
      }
    }
  }

  for (const node of nodes) {
    if (!visited.has(node)) {
      dfs(node);
    }
  }

  return [...articulation];
}

Why >= matters

For a bridge:

low[v] > disc[u]

For an articulation point:

low[v] >= disc[u]

If the subtree can only return to u itself, removing u still disconnects the subtree.

Cycles and redundancy

A cycle can provide an alternate route.

For a triangle:

A
|\
| \
B--C

no vertex is an articulation point.

Removing any one vertex leaves the other two connected.

Common structures

Chain:

A -- B -- C -- D

Internal vertices such as B and C are articulation points.

Star:

    B
    |
C -- A -- D
    |
    E

The center A is an articulation point.

Complete graphs with at least three vertices have no articulation point.

Real-world applications

Computer networks

Routers and switches can be vertices and links can be edges.

Articulation points reveal devices whose failure partitions the network.

Data centers

Critical gateways or network devices can be identified structurally and then protected with redundancy.

Transportation networks

Stations or intersections that connect otherwise separate regions may be articulation points.

Social graphs

A person or organization can be the only structural connector between two groups.

Infrastructure analysis

Articulation-point analysis can provide an initial structural view of single points of failure.

Important modeling caveat

Real systems may include failover, capacity, direction, load balancing, physical constraints, or probabilistic failure.

Articulation-point analysis only reflects the graph model provided.

It should therefore be treated as a structural connectivity analysis, not a complete reliability model.

Biconnected graphs

An undirected connected graph with no articulation point is biconnected or 2-vertex-connected.

Removing any single vertex does not disconnect it.

Biconnected components

Articulation points separate a graph into biconnected blocks.

These structures are useful for graph decomposition and connectivity queries.

Block-cut tree

A graph can be transformed into a block-cut tree containing:

• articulation-point nodes,
• biconnected-component nodes.

This gives a higher-level view of graph structure.

Articulation point vs centrality

Articulation points are binary:

critical / not critical

Betweenness centrality measures how often a vertex lies on shortest paths.

A vertex can have high centrality without being an articulation point.

Undirected graph assumption

The classic low-link algorithm described here applies to undirected graphs.

Directed cut-vertex problems have different connectivity semantics and require different treatment.

Edge cases

• one vertex,
• two vertices,
• disconnected graphs,
• DFS root with one child,
• DFS root with multiple children,
• self-loops,
• parallel edges / multigraphs.

For multigraphs, tracking only the parent vertex may be insufficient; edge IDs are safer.

Complexity

With adjacency lists:

Time:  O(V + E)
Space: O(V)

This is much better than brute-force removal.

TypeScript

type Graph = Record<string, string[]>;

function findArticulationPoints(
  graph: Graph
): string[] {
  const nodes = new Set<string>();

  for (const [u, neighbors] of Object.entries(graph)) {
    nodes.add(u);

    for (const v of neighbors) {
      nodes.add(v);
    }
  }

  const visited = new Set<string>();
  const disc = new Map<string, number>();
  const low = new Map<string, number>();
  const parent = new Map<string, string>();
  const result = new Set<string>();

  let time = 0;

  function dfs(u: string): void {
    visited.add(u);

    disc.set(u, ++time);
    low.set(u, disc.get(u)!);

    let children = 0;

    for (const v of graph[u] ?? []) {
      if (!visited.has(v)) {
        children++;
        parent.set(v, u);

        dfs(v);

        low.set(
          u,
          Math.min(low.get(u)!, low.get(v)!)
        );

        const isRoot = !parent.has(u);

        if (isRoot && children > 1) {
          result.add(u);
        }

        if (
          !isRoot &&
          low.get(v)! >= disc.get(u)!
        ) {
          result.add(u);
        }
      } else if (v !== parent.get(u)) {
        low.set(
          u,
          Math.min(low.get(u)!, disc.get(v)!)
        );
      }
    }
  }

  for (const node of nodes) {
    if (!visited.has(node)) {
      dfs(node);
    }
  }

  return [...result];
}

Common mistakes

• using the bridge condition > instead of articulation condition >=,
• forgetting the separate DFS-root rule,
• treating the parent edge as a back edge,
• processing only one connected component,
• applying the undirected algorithm directly to directed graphs,
• assuming high degree automatically means critical,
• ignoring destination-only vertices,
• mishandling parallel edges.

Summary

Articulation points reveal critical vertices whose removal increases the number of connected components.

The Tarjan-style DFS uses:

disc[u]
low[u]

For a non-root vertex:

low[child] >= disc[u]

indicates that the parent can be an articulation point.

For a DFS root:

more than one DFS child

is the critical condition.

The algorithm runs in:

O(V + E)

and is a fundamental tool for structural reliability and connectivity analysis.