Articulation Points

Overview

The Articulation Points algorithm finds cut vertices in a graph — nodes whose removal would disconnect the graph (or increase the number of connected components). Articulation points represent critical nodes and potential vulnerabilities in a network.

Concepts

Articulation Point

An articulation point (also called a cut vertex) is a node in an undirected graph whose removal, along with all its incident edges, increases the number of connected components. Removing an articulation point splits a connected part of the graph into two or more separate parts.

Articulation point detection is closely related to bridge detection. A bridge edge always connects to at least one articulation point (unless the bridge connects two leaf nodes). However, an articulation point does not necessarily have a bridge edge.

Articulation point detection is important for:

• Network reliability: Identifying single points of failure in infrastructure or communication networks.
• Graph structure analysis: Finding the biconnected components of a graph.
• Critical node protection: Prioritizing the protection or redundancy of critical nodes.

Considerations

• The algorithm treats all edges as undirected.
• Isolated nodes are not articulation points.

Example Graph

GQL
INSERT (A:default {_id: "A"}), (B:default {_id: "B"}),
       (C:default {_id: "C"}), (D:default {_id: "D"}),
       (E:default {_id: "E"}), (F:default {_id: "F"}),
       (A)-[:default]->(B), (B)-[:default]->(C),
       (C)-[:default]->(A), (C)-[:default]->(D),
       (D)-[:default]->(E), (E)-[:default]->(F),
       (F)-[:default]->(D)

Run Mode

Returns:

Find all articulation points:

GQL
CALL algo.articulationpoints() YIELD nodeId, isCutVertex

Result:

Stream Mode

Returns the same columns as run mode, streamed for memory efficiency.

GQL
CALL algo.articulationpoints.stream() YIELD nodeId, isCutVertex
RETURN collect_list(nodeId)

Result:

Stats Mode

Returns:

GQL
CALL algo.articulationpoints.stats() YIELD nodeCount, cutVertexCount

Result:

Write Mode

Computes results and writes them back to node properties. The write configuration is passed as a second argument map.

Write parameters:

Writable columns:

Returns:

GQL
CALL algo.articulationpoints.write({}, {
  db: {
    property: "is_cut"
  }
}) YIELD task_id, nodesWritten, computeTimeMs, writeTimeMs