Bracing squaregraphs (and other rhombus tilings)

A bookshelf or other structure made only of vertical and horizontal beams will easily fall over unless its joints are very strong, because axis-parallel structures are not inherently rigid. The vertical beams can tilt away from being perpendicular to the horizontals, without changing the relative spacing of the joints, and that can lead to books all over the floor. Here’s an example from a 2011 earthquake at the Smithsonian that didn’t get quite that far, but did damage some shelves beyond repair:

Triangular bookshelves would be annoying for different reasons, but they wouldn’t collapse like this, because triangular structures are more rigid: there is only one triangle that three sides of fixed lengths can form, unlike squares and rectangles which can flex into rhombi and parallelograms without changing their side lengths. So the standard solution to the bookshelf rigidity problem is to add cross bracing, diagonal beams built into shelves or other rectangular structures that make them similarly rigid. But which parts to brace? Even if every vertical and horizontal segment of a square bookshelf is allowed to flex independently of the other ones on its same line, bracing all the squares of the bookshelf would be too many. The vertical segments in each row of squares must stay parallel (in any flex small enough to avoid self-crossings), and similarly the horizontal segments in each column of squares must stay parallel. So a square grid with \(r\) rows and \(c\) columns has only \(r+c-1\) degrees of freedom in its shape (the relative angles among the verticals of each of the \(r\) rows and the horizontals of each of the \(c\) columns), far fewer than the \(rc\) braces that would be obtained by bracing all the squares.

A beautiful theory showing how to minimally brace any square (or rectangular) grid, connecting this grid bracing problem to the connectivity of bipartite graphs, was developed in the late 1970s and early 1980s by Ethan Bolker, Henry Crapo, Jenny Baglivo, and Jack Graver.^1 2 Their idea was to represent the grid and its bracing more abstractly, as a graph, whose vertices represent the rows and columns of grid squares. A braced square can be represented as an edge in this graph:

An edge in this graph, or more generally any chain of edges, fixes the relative angles between the vertical edges in the rows that it connects, and the horizontal edges of the columns. So if the whole graph is connected, as it is in the figure, all of these angles are fixed, and the grid is made rigid. In particular, any spanning tree of the complete bipartite graph on the rows and columns (such as the spanning tree shown in the figure) provides a bracing pattern that will suffice to make the grid rigid. It is also necessary for rigidity that the bracing pattern contain a spanning tree: any set of braces including a cycle is redundant, with one of the braces removable without changing the possible motions of the braced grid, and any forest that is not a tree has too few braces to eliminate all of the degrees of freedom. So a grid is braced rigidly if and only if its graph is connected, and the minimal rigid bracings are exactly the spanning trees.

The same theory can be (and has been) generalized in multiple ways. A grid is “double braced” if every brace is redundant: you can remove any one brace and the whole structure will stay rigid. This is true if and only if the corresponding graph has the property that you can remove any one edge and the whole graph will remain connected, which is true exactly for the connected bridgeless graphs. A version with directed graphs applies to bracing by strings or wires, strong under tension but useless under compression. These constrain the sides of the squares from turning only in one direction: if one side turns clockwise, the other side is forced to turn clockwise, or vice versa, but not both ways. So we can represent a tension brace in a square by a directed edge. The edge is directed from the square’s row to its column when a clockwise turn of the vertical sides in the row would force a clockwise turn of the horizontal sides in the column, and in the other direction otherwise. Then, the whole structure is rigid under this sort of tension bracing if and only if the resulting directed graph is strongly connected.

For this theory to work, it is necessary that the braced structure consist of quadrilaterals with parallel sides, but they don’t have to be squares: the same thing works for grids of rectangles, rhombi, or parallelograms. It would work for the deformed square grid in the right of the second figure, for instance. It’s also not necessary for the quadrilaterals to be connected in the pattern of a square grid. In 2006, Ture Wester observed that the same method should work for the rhombic version of the Penrose tiling, for instance, but was very vague about boundary conditions (not distinguishing carefully between infinite tilings and finite patches of them).³ The correct boundary conditions are that this works for any tiling of a disk in the plane by finitely many parallel-sided quadrilaterals. For such tilings, one can group the quadrilaterals into zones, sequences of quadrilaterals connected edge-to-edge on opposite sides, so that each quadrilateral belongs to two zones (giving it a zone by itself if two opposite sides are both on the boundary of the disk). Without bracing, the shared parallel sides in each zone can turn independently of any other motion of the tiling; this is the part that requires that the tiled area be a disk rather than an annulus or more complicated shape, so that the two parts of the graph separated by each zone are disconnected from each other and can move independently. And the overall shape of the tiling is completely determined by the angles of the shared sides of all of its zones. Therefore, the number of degrees of freedom (factoring out motions in which the tiling translates without rotation, or rotates rigidly) is exactly one less than the number of zones. Any set of braced quadrilaterals can be represented as a subgraph of the intersection graph of the zones, and after the calculation of degrees of freedom, the same argument as for grids shows that the tiling is rigid if this subgraph connects all the zones, that it is double braced if this subgraph is connected and bridgeless, or that it is tension braced if the directed version of this subgraph is strongly connected.

So as Wester stated, this does work for rhombic Penrose tilings, as long as one considers disk-shaped patches of the tilings. Similar, it works for (simply-connected) polyominoes, or disk-shaped patches of the rhombille tiling. It also works for squaregraphs, planar graphs in which all interior vertices have degree at least four and all interior faces are quadrilaterals, as long as those quadrilaterals are drawn with parallel sides. One of my old papers shows that these drawings always exist,⁴ and another shows how to optimize them to avoid sharp angles.⁵. In all of these cases, the tiling can be made rigid by bracing tiles forming a spanning tree of its zones, doubly rigid by bracing tiles forming a bridgeless spanning subgraph, or rigid for tension bracing by adding braces that form a strongly connected graph.

However, some algorithmic aspects of this theory may depend more strongly on the fact that for square grids, the intersection graphs of their zones have a very simple structure. Square grids have complete bipartite zone intersection graphs, but more general tilings of disks by parallel-sided quadrilaterals have arbitrary circle graphs and squaregraphs have triangle-free circle graphs. Extending a partial bracing to a minimal rigid bracing is just a matter of extending a forest to a spanning tree, easy in all graphs, but the corresponding problem for tension bracing is more complicated. Gabow and Jordán solve it for square grids (equivalently, adding as few edges as possible to a bipartite directed graph to make it strongly connected, while respecting its given bipartition) in linear time.⁶ But it is not at all obvious that it’s as easy to extend a directed subgraph of a circle graph to a minimal strongly connected subgraph of the same circle graph.

(Discuss on Mastodon)