Realizations of Rigid Graphs

Rigid structures have been a subject of scientific work since the construction of trusses. Trusses consist of bars and joints and they are modeled by graphs with edges and vertices. Properties of rigidity can be studies on the mathematical objects., These rigid graphs are the main basis of this project. A graph with given edge lengths is rigid, if there are only finitely many possibilities to draw the graph with the respective lengths. Such a drawing, or more precisely the coordinates of the vertices, is a realization of the graph. We are interested in the number of realizations. Just recently we developed an algorithm for computing them for the two- dimensional case. Now, the aim of this project is to analyze the number of realizations. We investigate classes of graphs with rather high or low number of realizations. These classes help to find bounds on the numbers. Furthermore, we investigate realizations of rigid graphs in three-dimensional space. The property of rigidity can also be extended to more general objects, like so called hypergraphs. In all these cases much less is known so far. Aim of the project is to achieve a deeper understanding of these rigid objects. The project connects different mathematical disciplines like graph theory, combinatorics, symbolic computation and algebraic geometry. This variety enables us to combine methods from several domains and obtain new results. Rigid graphs play an important role in applications, like computer-aided design, structural molecular biology, sensor networks, robotics, materials science, and machine learning. These applications show that is important to understand the underlying models on a basic research point of view.

The aim of the project was the analysis of realizations of rigid graphs. A graph consists of vertices which are connected by edges. Graphs can be called rigid, when there are only finitely many different ways to draw them in the plane for given edge lengths. Two drawings are considered different, if they cannot be transformed to each other by rotations and translations. There were already methods for counting the drawings (also called realizations). In this project we improved them. With the current methods we can compute the number of realizations for many graphs much faster. We extended the problem also to other situations, for instance to realizations on the sphere. A new algorithm from this project counts these spherical realizations. We also obtained first results on realization counts in the three dimensions. In particular we were interested in graphs with very few realizations, also in rigid graphs which have just one realization (up to reflection). On the other hand we found graphs with rather high realization numbers. Some graphs have infinitely many realizations for specific edge lengths. These realizations can be visualized in a motion. We then call each of them a flexible realization. In many cases vertices may overlap during the whole motion. In this project we determined when some classes of graphs have realizations without overlapping vertices. Furthermore, we provided results on flexible realizations on the sphere, symmetric flexible realizations and three dimensional flexible realizations for special graphs. In all cases algebraic geometry played an important role. While the results can be explained by graph theory, the proofs need applications of algebraic methods. These are based on the equations imposed by the edge lengths. Realizations of rigid graphs play a role in applications. A first step towards applications into algebraic statistics and computational biology has been made.