Realizations and Constructions of Minimally Rigid Graphs

Year: 2018 Authors: Georg Grasegger

Core claim

Henneberg-type constructions and rigidity theory provide a way to build and realize minimally rigid graphs in 2D and 3D.

Topics

rigidity theory, graph realizations, Henneberg constructions, physical construction

Domains

graph theory, discrete geometry, algebraic geometry, rigidity theory, mathematical sculpture, structural design, architecture, craft

Methods

Henneberg steps, quadratic equations, Gröbner bases, physical prototyping

Media

magnetic bars, wooden sticks and screws, drinking straws, beads

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2018 Conference Proceedings

Realizations and Constructions of Minimally Rigid Graphs

Georg Grasegger

Johann Radon Institute for Computational and Applied Mathematics (RICAM), Austrian Academy of Sciences (ÖAW), Austria; georg.grasegger@ricam.oeaw.ac.at

Abstract

We present the mathematical basics of minimally rigid graphs in two and three dimensions. Using this theory we show how to actually construct rigid structures with different materials.

Introduction

Rigid structures in two and three dimensions have been investigated by mathematicians and scientists from several disciplines. Such structures consist of bars and joints and are usually modeled by graphs. Nowadays, rigid structures are also used in materials science, bioinformatics, architecture and in many other fields.

Let $G=(V,E)$ be a graph with vertices $V$ and edges $E$ and let $\lambda :E⟶\mathbb{R}$ be a map associating a length to each edge. We would like to know whether there exist coordinates for the vertices such that the graph can be drawn with the respective edge lengths. We call these coordinates a realization of the graph which is compatible with $\lambda$ .

A graph is called rigid, if there are only finitely many realizations up to translations and rotations (if the given edge lengths are generic enough, i.e., there might be special non-generic lengths for which the graph is flexible, e.g., the three-prism graph in Figure 3 when all edges have equal lengths). A rigid graph is minimally rigid, if it is rigid and removing any edge results in a non-rigid (flexible) graph (see Figure 1). Minimally rigid graphs are also called Laman graphs.

(a) flexible

(b) minimally rigid

(c) rigid (overdetermined) Figure 1: Graphs in the plane with different rigidity properties

Minimally Rigid Graphs

It is known from Henneberg [4] how to construct all minimally rigid graphs starting from a single edge. These two rigidity preserving constructions can be seen in Figure 2 and 3. In a Henneberg step of type 1, a vertex incident to two new edges is added to a given graph. In type 2, an edge of a given graph is deleted, a new vertex connected to the endpoints of the deleted edge and to a third vertex of the given graph is added.

(a) Type 1

(b) Type 2 Figure 2: Henneberg steps of both types; a dashed line indicates that this might be an edge of the given graph but there does not need to be an edge.

Grasegger

Figure 3: Construction of the three-prism graph using Henneberg steps.

Planar rigid graphs can be easily built with different kinds of materials (e.g. magnetic bars as in Figure 4). Using colored wooden sticks and screws, we also constructed non-planar, minimally rigid graphs in the plane (with some edge crossings), see for example Figure 5a. Note that we consider the mathematical graph to be in the plane, where of course the wooden sticks in the physical object have to be placed in layers to allow crossings. In order to experience the rigidity, we only use joints that would theoretically allow movements parallel to the plane (e.g. screws, balls, rivets).

(a) Simple rigid graphs

(b) Sierpinksi graph with magnetic bars.

(a) Rigid graph with 12 vertices Figure 5: Minimally rigid graphs made from wooden sticks and screws.

Figure 4: Minimally rigid graphs with magnetic bars. (b) Rigid graph with 54 vertices

Minimally rigid graphs have finitely many realizations (see Figure 6). This number of realizations is a current topic of research. The basic approach is to solve the system of quadratic equations of the form $(x_i-x_j{)}^2+(y_i-y_j{)}^2={\lambda }_{i,j}$ , where $(x_i,y_i)$ are the coordinates of the vertex $i$ . This is, however, not efficient and can only be done for rather small graphs. Recent research shows how to compute the number of complex realizations in a more efficient way (see [2]). For the purpose of drawing, real realizations are more interesting. Research in this direction can be found for instance in [5]. In Figure 6 we can see all real realizations of the three-prism graph (up to reflection) ${}^1$ . If we allow the same graph in three dimensions it will be flexible and the motion covers all rigid states in the plane. A video of this motion can be found at www.koutschan.de/data/laman.

Realizations and Constructions of Minimally Rigid Graphs

Figure 6: Realizations of the three-prism graph, with vertices $1,\dots ,6$ , edges $\{1,2\}$ , $\{1,3\}$ , $\{1,4\}$ , $\{2,3\}$ , $\{2,5\}$ , $\{3,6\}$ , $\{4,5\}$ , $\{4,6\}$ , $\{5,6\}$ and length $2,2,7/4,2,197/100,27/10,11/5,29/10,43/20$ .

Minimally Rigid Graphs in 3D

Similar to the two-dimensional case, three-dimensional minimally rigid graphs can be built up in steps starting from the triangle graph (see [7] and Figure 7). Type 1 adds a vertex with three edges. In type 2 an edge of a given graph is deleted, a new vertex is added and it is connected to the endpoints of the deleted edge and to two other vertices of the given graph. Both type 3 steps delete two edges of a given graph and add a new vertex. This vertex is connected to the endpoints of the deleted edges and to one or respectively two other vertices of the given graph such that the new vertex is connected by five edges. Constructions of types 1 and 2 preserve rigidity whereas not every graph which is constructed using a step of type 3 is indeed minimally rigid. It is known from [7] that every minimally rigid graph can be built using these constructions.

Figure 7: Henneberg steps in dimension 3; a dashed line indicates that this might be an edge of the given graph but there does not need to be an edge.

For the three-dimensional case, rigidity can only be tested by using Gröbner bases with random edge lengths allowing complex coordinates. So far all minimally rigid graphs up to 10 vertices were constructed and tested (see [1, 3]). It turns out that there are only six minimally rigid graphs with at most six vertices (see Figure 8).

Figure 8: All nonisomorphic minimally rigid graphs in $3D$ up to 6 vertices constructed using straws and filament.

Grasegger

Simple minimally rigid graphs can be constructed using drinking straws connected with filaments ${}^2$ (see Figure 8) or beads (compare [8]). In order to practically experience rigidity, we recommend building such graphs using spherical joints, e.g. by magnetic bars and metallic balls (see Figure 9). The magnetic bars can be bought or self-made by gluing small magnets to straws or sticks.

Figure 9: Minimally rigid graphs in 3D.

Summary and Conclusions

Since it is easy to state the problem of rigid structures, it is a suitable topic for exploring in the intersection of mathematics, art and education. On the one hand mathematical equations and their solutions can be investigated and on the other hand creative rigid structures are actually built with different materials. Furthermore, it allows to get in touch with current research, since during exploration with the material you might come across several yet unsolved questions, for instance the characterization of three-dimensional minimally rigid graphs. Rigid constructions are also used in more general settings like tensegrities (see for instance [6]) or body-and-bar frameworks.

References

[1] E. Bartzos, I. Emiris, J. Legersky, and E. Tsigaridas. “On the Maximal Number of Real Embeddings of Spatial Minimally Rigid Graphs.” Technical Report 1802.05860v1, arXiv, 2018. [2] J. Capco, M. Gallet, G. Grasegger, C. Koutschan, N. Lubbes, and J. Schicho. “The Number of Realizations of a Laman Graph.” SIAM Journal on Applied Algebra and Geometry, vol. 2, no. 1, 2018, pp. 94–125. [3] G. Grasegger, C. Koutschan, and E. Tsigaridas. “Lower Bounds on the Number of Realizations of Rigid Graphs.” Experimental Mathematics, 2018. to appear, arXiv:1710.08237. [4] L. Henneberg. “Die graphische Statik der starren Körper.” In Encyklopädie der mathematischen Wissenschaften mit Einschluss ihrer Anwendungen, vol. IV, 1903, pp. 345-434. [5] B. Jackson and J. C. Owen. “Equivalent Realisations of a Rigid Graph.” Discrete Applied Mathematics, 2018. In press, DOI: 10.1016/j.dam.2017.12.009. [6] A. Pugh. An Introduction to Tensegrity. University of California Press, Berkeley, 1976. [7] T.-S. Tay and W. Whiteley. “Generating Isostatic Frameworks.” Topologie Structurale, vol. 11, 1985, pp. 21-69. [8] C.-C. Tsoo and B.-Y. Jin. “Designing Skeletal Polyhedral Sculptures Inspired by Octet-Truss Systems and Structural Inorganic Chemistry with Bugle Beads.” Bridges Conference Proceedings, Waterloo, Ontario, Canada, July 21–31, 2017, pp. 483–486.