In the mathematics of structural rigidity, grid bracing is a problem of adding cross bracing to a rectangular grid to make it into a rigid structure. If a two-dimensional grid structure is made with rigid rods, connected at their ends by flexible hinges, then it will be free to flex into positions in which the rods are no longer at right angles. Cross-bracing the structure by adding more rods across the diagonals of its rectangular or square cells can make it rigid.
The problem can be translated into graph theory by constructing a graph in which the graph vertices represent rows and columns of the grid, and each edge represents a cross-braced cell in a given row and column. The grid is rigid if and only if the resulting graph is a connected graph. Every minimal system of cross-braces that makes the grid rigid corresponds to a spanning tree of a complete bipartite graph.
The graph-theoretic solution to the grid bracing problem has been generalized to double bracing, in which the grid should remain rigid even if one cross-brace fails, and to tension bracing, in which the diagonals of a grid are braced by wires and strings that can crumple to a shorter length but cannot be stretched to be longer. For double bracing, the rigid solutions correspond to biconnected graphs; for tension bracing, they correspond to strongly connected graphs. In both cases, the minimal solutions correspond to Hamiltonian cycles.