In the mathematics of structural rigidity, grid bracing is a problem of adding cross bracing to a square grid to make it into a rigid structure. It can be solved optimally by translating it into a problem in graph theory on the connectivity of bipartite graphs.
Problem statement
The problem considers a framework in the form of a square grid, with rows and columns of squares. The grid has edges, each of which has unit length and is considered to be a rigid rod, free to move continuously within the Euclidean plane but unable to change its length. These rods are attached to each other by flexible joints at the vertices of the grid. A valid continuous motion of this framework is a way of continuously varying the placement of its edges and joints into the plane in such a way that they keep the same lengths and the same attachments, but without requiring them to form squares. Instead, each square of the grid may be deformed to form a rhombus, and the whole grid may form an irregular structure with a different shape for each of its faces, as shown in the figure.
Unlike squares, triangles made of rigid rods and flexible joints cannot change their shapes: any two triangles with sides of the same lengths must be congruent (this is the SSS postulate). If a square is cross-braced by adding one of its diagonals as another rigid bar, the diagonal divides it into two triangles which similarly cannot change shape, so the square must remain square through any continuous motion of the cross-braced framework. (The same framework could also be placed in the plane in a different way, by folding its two triangles onto each other over their shared diagonal, but this folded placement cannot be obtained by a continuous motion.) Similarly, if all squares of the given grid were cross-braced in the same way, the grid could not change shape; its only continuous motions would be to rotate it or translate it as a single rigid body. However, this method of making the grid rigid, by adding cross-braces to all its squares, uses many more cross-braces than necessary. 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.
Graph theoretic solution
As originally observed, the grid bracing problem can be translated into a problem in graph theory by considering an undirected bipartite graph that has a vertex for each row and column of the given grid, and an edge for each cross-braced square of the grid. 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 cross-braced squares. Any overbraced but rigid cross-bracing (with more than this number of cross-braced squares) can be reduced to a minimal cross-bracing by finding a spanning tree of its graph. More generally, the number of degrees of freedom in the shape of a cross-braced grid is equal to the number of connected components of the bipartite graph, minus one. If a partially braced grid is to be made rigid by cross-bracing more squares, the minimum number of additional squares that need to be cross-braced is this number of degrees of freedom, and a solution with this number of squares can be obtained by adding this number of edges to the bipartite graph, connecting pairs of its connected components so that after the addition there is only one remaining component.
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. This version allows both diagonals of a single square to be used, but it is not required to do so. In this version, a double bracing of a grid corresponds in the same way to an undirected bipartite multigraph that is connected and bridgeless (every edge belongs to at least one cycle). The minimum number of diagonals needed for a double bracing is . In the special case of grids with equal numbers of rows and columns, the only double bracings of this minimum size are Hamiltonian cycles, so determining whether one exists within a larger bracing is NP-complete. However, it is possible to approximate the smallest double bracing subset of a given bracing within a constant approximation ratio.
