Grid bracing

Cross-bracing the structure by adding more rods across the diagonals of its rectangular or square cells can make it rigid.

Every minimal system of cross-braces that makes the grid rigid corresponds to a spanning tree of a complete bipartite graph.

The grid bracing problem asks for a description of the minimal sets of cross-braces that have the same effect, of making the whole framework rigid.

They proved that the cross-braced grid is rigid if and only if this bipartite graph is connected.

It follows that the minimal cross-bracings of the grid correspond to the trees connecting all vertices in the graph, and that they have exactly

[1][2][3][4] Another version of the problem asks for a "double bracing", a set of cross-braces that is sufficiently redundant that it will stay rigid even if one of the diagonals is removed.

[1] In the same bipartite graph view used to solve the bracing problem, a double bracing of a grid corresponds to an undirected bipartite multigraph that is connected and bridgeless, meaning that every edge belongs to at least one cycle.

[1] In the special case of grids with equal numbers of rows and columns, the only double bracings of this minimum size are Hamiltonian cycles.

[5] An analogous theory, using directed graphs, was discovered by Jenny Baglivo and Jack Graver (1983) for tension bracing, in which squares are braced by wires or strings (which cannot expand past their initial length, but can bend or collapse to a shorter length) instead of by rigid rods.

The braced structure is rigid if and only if the resulting graph is strongly connected.

[6] If a given set of braces is insufficient, additional bracing needs to be added, corresponding in the graph view to adding edges that connect together the strongly connected components of a graph.

In this way problem of finding a minimal set of additional braces to add can be seen as an instance of strong connectivity augmentation, and can be solved in linear time.