Bridges and articulation points

In September 2024 a stretch of Kerey-Zhanibek Khandar Street, the road to the Medeu skating rink, was closed for repairs several nights in a row, from eleven in the evening to six in the morning; only ambulances and other emergency services were let through. There was no way round: one road leads into the gorge. A big city has thousands of such streets, only usually there is a dead end behind them, not a valley. Below are the streets of Almaty from OpenStreetMap, from Almaty-2 station to Big Almaty Lake, and one pass of depth-first search that finds all such streets at once. Click a street to close it, or a button under the map to see the largest finds.

Two roads into the mountains glow red. Dulati Avenue, which turns into Alma-Arasan Street, is the only way into the Big Almaty Gorge: close it at the edge of the city, and 128 crossroads and 44 km of streets, Alma-Arasan and the road to the lake among them, are left without a link to the city. Kerey-Zhanibek Khandar Street holds as many crossroads, 128, and 32.7 km of streets up to Medeu. In the city itself the picture is different. Of 3005 bridges, 2201 lead to a single dead-end crossroads, and the others cut off a yard, a lane, a cottage settlement. Close almost any street of the grid in the centre and there is a detour of a couple of blocks; it shows up in blue.

The idea

The two things this article looks for are defined the same way. A bridge is an edge whose removal makes the graph fall apart: some two vertices that were connected are connected no longer. An articulation point is such a vertex. An edge is a bridge exactly when it lies on no cycle: a cycle is the detour.

The direct way, remove an edge and check whether its ends are connected, costs one traversal of the graph per edge. For 15,169 pieces of street that is 15,169 traversals, and in a larger network the square of its size. Depth-first search handles all the edges in one pass, because in an undirected graph it leaves behind a very simple picture. The edges it walked along form a tree. Each of the other edges connects a vertex with its ancestor in that tree, with a vertex higher up the same branch. There are no edges between different branches; this is proved below.

Let a tree edge lead from u down to v. The subtree of v, the vertices the search reached through v, is connected to the rest of the graph by this edge and perhaps by back edges going up. If even one of them climbs to u or higher, that is a detour. If none does, the edge u–v is a bridge. To answer for all edges at once, it is enough to know for each vertex how high one can climb from its subtree.

Mark each vertex with its entry time tin, the number under which the search reached it. For a vertex v compute low, the earliest entry time reachable from its subtree by one back edge. A tree edge u–v is a bridge if low(v) > tin(u): from the subtree you cannot climb even to u. A vertex u is an articulation point if it has a child v with low(v) ≥ tin(u): from that child's subtree you cannot climb above u, and without u it is cut off. There is nobody above the root of the search, and the root has its own rule: it is an articulation point if it has more than one child in the tree.

low is computed by the same search, bottom up: it is the minimum of the vertex's own tin, the tin of the ends of back edges leaving it, and the low of its children. When the search returns from v to u, low(v) is already final, and both checks are made on the spot.

How it works step by step

A small neighbourhood at the foot of the mountains: a grid of six crossroads, two parallel streets to crossroads G, a road up to the triangle H, I, J, and a dead end K. Under each letter are tin and low. Solid lines are the search tree, dashed ones back edges. Click any crossroads to start the search from it.

Follow crossroads H. The search enters it from F with tin = 7, passes I and J, and the back edge J–H brings low(J) down to 7, after which the seven rises into low(I). When the search returns from I to H, low(I) = tin(H) = 7. The strict inequality does not hold, so the street H–I is not a bridge: the triangle goes round it. The non-strict one holds, so H is an articulation point: everything below hangs on H itself. That is the difference between > and ≥. A bridge is a question of whether the edge can be bypassed, an articulation point of whether the vertex can. A back edge that arrives at H itself bypasses the edge H–I, but not H.

The root A is a special case. The condition low(B) ≥ tin(A) always holds for it, since nobody is above the root, but that does not make it an articulation point: in the tree A has one child, and without A everything else hangs on that child. Start the search from F and the root will have three children, one towards the grid, G and H, and F becomes an articulation point by the root rule. The bridges and points are the same, although all the numbers under the letters are different: the answer does not depend on where you started.

Why the test is right

All the work rests on the lemma: an undirected depth-first search has no sideways edges, and one number low is enough. Take another spanning tree, for example the breadth-first search tree, and edges from a subtree can go into neighbouring branches. Then you have to track both the earliest and the latest number a subtree reaches. That is how the first linear algorithm for bridges works; more on it in the history.

The trap: two streets between the same crossroads

You must not go back along the edge you came by: that is not a detour but the same edge. Very often this is written as “do not go to the parent”, comparing a neighbour with the parent vertex. While there is at most one edge between two vertices, it makes no difference. But road graphs have two different streets between the same crossroads: the two carriageways of a divided avenue, half a ring of an interchange, a street and a parallel service road. In the scene above switch “Skip the parent” to “by its vertex (a mistake)”. The search throws out the second street F–G together with the first and declares F–G a bridge, although if one of the two streets is closed, G can be reached by the other.

In the Almaty graph 81 pairs of crossroads are connected by two or even three different pieces of street. A search with the vertex check finds 3030 bridges instead of 3005, and 25 of them are false. The correct check remembers the number of the edge it came by and skips only that edge; all the listings below are written this way.

For articulation points this mistake, oddly enough, is harmless. The extra edge to the parent would give low(v) = tin(u), and the non-strict inequality low(v) ≥ tin(u) allows that anyway: two streets to the same crossroads do not help you get around the crossroads itself. So code that looks only for articulation points is often written “by the vertex”, and it is correct. The trouble starts when the same code is taken for bridges.

Code

The search without recursion, with its own stack of frames: a vertex, the edge it was entered by, and a position in the list of neighbours. The demo is the neighbourhood from the scene above.

Bridges are printed in the order the search finds them: first I–K, then F–H. The verdict on an edge is given when the search returns up along it, and it returns from the deepest places first.

Now the whole city. The root of the search is a vertex “the rest of the world”: this way, for each bridge it is clear at once which side is cut off from the city, the side with the subtree. Along the way the program counts how many crossroads and metres of streets each subtree has, and finds the places that hang on a single street: bridges with no other bridges above them on the way to the root.

bridges: 3005, of them to a single dead-end crossing: 2201
articulation points: 2552
components without bridges: 3006; the one with the world outside: 8450 crossings (72.1%)
deepest search: 2453 vertices on the stack

The search stack over the streets of Almaty grows to 2453 vertices, while Python's default recursion limit is a thousand calls. So a recursive version would crash on this city. More on stack depth in the article on depth-first search.

What is left between the bridges

Bridges and articulation points cut the graph into pieces, and the pieces come in two kinds, depending on what may be broken.

If one edge may be broken, the pieces are components without bridges: remove all the bridges, and what stays connected is one component. Inside it any one street can be closed without cutting off a single crossroads. Almaty has 3006 such components, but almost all of them are lone crossroads at the ends of dead ends. The main one, together with the world beyond the edge of the map, is 8450 crossroads of 11,723, 72.1 %. Shrink each component to a point, and the bridges link the points into a tree: a cycle of components would mean that some bridge lies on a cycle.

If one vertex may be broken, the pieces are blocks, or biconnected components: maximal pieces that do not fall apart when any single vertex is removed. Each edge lies in exactly one block, and an articulation point in several at once: it is what stitches the blocks together. Switch the small neighbourhood scene to “blocks”: there are five of them, the grid, the pair of streets F–G, the bridge F–H, the triangle H, I, J and the bridge I–K. Crossroads G is in the same bridgeless component as the grid, since the two streets to it are the detour, but in a separate block: both streets meet at F, and without F there is no way to G.

Blocks have an exact characterisation. In 1932 Hassler Whitney proved that a graph with three or more vertices does not fall apart when one vertex is removed if and only if any two of its vertices are joined by two paths with no common intermediate vertices. For edges it is the same: a component without bridges is a place where any two vertices are joined by two paths with no common edges. Both statements are special cases of Menger's theorem on the number of disjoint paths, which is easiest to prove with flows.

The same search finds blocks if edges are pushed onto a stack as it meets them. When the search returns from v to u and sees low(v) ≥ tin(u), everything on the stack above the edge u–v, together with it, is one block.

What it costs

The search enters each vertex once and considers each edge twice, from both ends. The numbers tin and low, the subtree size and the checks on return are O(1) per vertex and edge. In total O(V + E) time and O(V + E) memory: the graph itself plus a few arrays the size of the number of vertices; blocks also need a stack of edges. The naive way, remove an edge and look for a detour by a traversal, pays O(V + E) for every edge, that is, O(E(V + E)).

A measurement on a grid city where each street survived with probability 0.6: many dead ends and bridges, as on the outskirts. The naive way looks for a detour by a search and stops as soon as it finds the other end, the way someone in a hurry would write it.

The naive way has a slope of about two: double the city and the time grows fourfold, because there are twice as many bridges, and each bridge requires walking the whole cut-off side together with the rest of the city. One search grows linearly. On a grid of 4900 crossroads the difference is already hundreds of times, and it grows with the city.

Where it is used

Networks that must survive a failure. Power engineers check a grid by the N−1 rule: it must withstand the failure of any one element, a line, a transformer, a generator, without cutting off consumers. A real check computes power flows, but a bridge is the crudest violation, visible without any calculation: one line with a whole district behind it. The same rule applies in backbone communication networks: two independent lines lead to a node, so that an excavator cutting one does not leave a city without communications.

Roads. For a road network, bridges are a list of places where repairs, an accident or a mudflow will cut people off from the city, and articulation points are crossroads where one interchange under repair will do the same. In the mountains and on the outskirts this list is long, in the grid of the centre almost empty: there almost any street can be bypassed, as the first scene shows.

One-way streets. A city without bridges can be made entirely one-way so that you can get from anywhere to anywhere: this is Robbins's theorem of 1939. Bridges have to stay two-way. The proof is the same depth-first search and the same numbers low; it is worked through in the article on strongly connected components.

Splitting a graph into parts. A graph is planar, drawable without edge crossings, if and only if each of its blocks is planar. So planarity tests, starting with the linear test of Hopcroft and Tarjan of 1974, first of all cut the graph into blocks. The next step of the same decomposition is triconnected components, where the graph does not fall apart even when any two vertices are removed.

History

Biconnected graphs were studied by Hassler Whitney back in the early 1930s; the 1932 paper is called “Non-separable and planar graphs”. A linear-time algorithm for blocks based on depth-first search appeared in the early 1970s with John Hopcroft and Robert Tarjan: in Tarjan's 1972 paper on depth-first search and in Hopcroft and Tarjan's “Algorithm 447”, printed in Communications of the ACM in June 1973, where a graph is divided into connected components and biconnected components in time proportional to the number of vertices and edges. The quantity this article calls low they called the lowpoint.

Tarjan treated bridges separately in a two-page note of 1974, “A note on finding the bridges of a graph”. Its point is that for bridges depth-first search is not required: any spanning tree will do. Tarjan numbers the vertices of the tree in postorder, computes for each the number of descendants and two numbers, the earliest and the latest number the subtree reaches by one non-tree edge. A tree edge is a bridge if both numbers stay within the subtree. Depth-first search removes the need for the second number: it has no sideways edges.

Problems

In the first problem you answer hundreds of thousands of questions “what will this closure cut off”, and among the tests is that city with parallel streets. In the second a crossroads is closed, and you count how many pairs of places lose their connection to each other; articulation points, subtree sizes and the difference between > and ≥ will all come in handy.