Realizations of Rigid Graphs^††thanks: Supported by the Austrian Science Fund (FWF): F5011-N15. Based on joint work with Jose Capco, Matteo Gallet, Georg Grasegger, Niels Lubbes, Josef Schicho, and Elias Tsigaridas.

The theory of rigid graphs forms a fascinating research area in the intersection of graph theory, computational algebraic geometry, and algorithms. The study of rigid structures, also called frameworks, was originally motivated by mechanics, and it goes back at least to the 19th century. Besides being a very interesting mathematical subject, rigid graphs and the underlying theory of Euclidean distance geometry have meanwhile found a large number of applications ranging from robotics and bioinformatics to sensor network localization and architecture.

Suppose that we are given a graph $G$ with edge set $E$. We consider the set of all possible realizations (embeddings) of the graph in the Euclidean plane such that the lengths of the edges coincide with some prescribed edge labeling $\lambda\colon E\rightarrow\mathbb{R}_{>0}$. Edges and vertices are allowed to overlap in such a realization. For example, suppose that $G$ has four vertices and is a complete graph minus one edge. Figure 1 shows all possible realizations of $G$ up to rotations and translations, for a certain edge labeling. We address the following problem:

For a given graph determine its number of realizations for a general edge labeling, up to rotations and translations.

Here we say that a property holds for a general edge labeling if it holds for all edge labelings belonging to a dense open subset of the vector space of all edge labelings.

The realizations of a graph can be considered as physical structures in the plane, which consist of rods that are connected by rotational joints. If a graph together with an edge labeling admits infinitely (resp. finitely) many realizations up to rotations and translations, then the corresponding planar structure is flexible (resp. rigid), see Figure 2.

A graph is called generically rigid (or isostatic) if a general edge labeling yields a rigid realization. No edge in a generically rigid graph can be removed without losing rigidity, that is why such graphs are also called minimally rigid in the literature. The complete graph on four vertices $K_{4}$ is for instance not considered to be minimally generically rigid, since for a general choice of edge lengths it will not have a realization: imagine you would have to add the missing edge in either of the realizations depicted in Figure 1 — for most prescribed lengths of the new edge this will not be possible, see also Figure 2. Hilda Pollaczek-Geiringer [9] and independently Gerard Laman [8] characterized the property of generic rigidity in terms of the number of edges and vertices of the graph and its subgraphs, hence such objects are also known as Laman graphs.

All finitely many realizations of a Laman graph can be obtained as the solution set of a system of quadratic polynomial equations, where the edge labels are either given by concrete numbers or interpreted as parameters. In general it is difficult to produce results on the number of real solutions of such systems. In such situations, one often switches to a complex setting; this also enables us to apply results from algebraic geometry. Hence, from now on, we consider edge labelings with complex numbers, and we are interested in the number of complex solutions, up to an equivalence relation on $\mathbb{C}^{2}$ generalizing the direct isometries of $\mathbb{R}^{2}$; this number is the same for any general edge labeling, so we call it the Laman number of the graph $G$, denoted by $\operatorname{Lam}(G)$. For some graphs up to $8$ vertices, this number had been computed using random values for the edge labels [7] — this means that it is very likely, but not absolutely certain, that these computations give the true numbers. Upper and lower bounds for Laman numbers are considered in [4, 10, 1]. Note that for many Laman graphs there exists a (real) edge labeling such that the number of real realizations equals precisely the Laman number. However, there are graphs for which the Laman number gives only an upper bound on the number of real realizations.

Our main result is a combinatorial algorithm that computes the number of complex realizations of any given Laman graph; it is much more efficient than just solving the corresponding nonlinear system of equations. The algorithm and its correctness proof are presented in detail in [2]. Using a supercomputer, we apply this algorithm to a large collection of Laman graphs and identify among all Laman graphs with $n$ vertices ($n\leq 12$) the one with the maximal Laman number. This allows us to derive better lower bounds on the number of realizations [5]. In the following, we provide a concise summary of these results, focusing on the main ideas and the algorithmic point of view.

We write $G=(V,E)$ to denote a finite graph $G$ with vertices $V$ and edges $E$. An edge $e$ between two vertices $u$ and $v$ is denoted by $\{u,v\}$; this notation expresses the fact that all graphs considered here are undirected.

Using nonnegative real labels for the edge lengths, the number of realizations in $\mathbb{R}^{2}$ for a general edge labeling is not well-defined, since it heavily depends on the actual labeling and not only on the graph. For example, the complete graph $K_{3}$ permits two different realizations (one being the reflection of the other) for almost all edge labelings that satisfy the triangle inequality, while it has none for all other labelings. In order to define a number that depends only on the graph, we switch to a complex setting. In order to keep notations simple, we take the convention that the edge labelings give the squared distances between vertices.

Our main interest is to count the number of realizations of generically rigid graphs, namely graphs for which almost all realizable labelings induce rigidity.

In order to set up a recursive formula for the degree of the map, we want to be able to handle the two factors $(x_{u}-x_{v})$ and $(y_{u}-y_{v})$ independently. To do this we duplicate the graph, and for technical reasons we allow a more general class of graphs. The resulting concept is roughly speaking a pair of graphs $(G,H)$ with a bijection between their sets of edges. We identify edges by this bijection.

We define the Laman number $\operatorname{Lam}(B)$ of a bigraph $B$ as the degree of an associated map defined in a similar way as $r_{G}$. Moreover, we show that the Laman number of a graph equals the Laman number of the corresponding bigraph.

The idea for proving the recursion formula in Theorem 2 is inspired by tropical geometry: we consider the equation system over the field of Puiseux series; an algebraic relation between Puiseux series implies a piecewise linear relation between their orders. We encode these piecewise linear relations in a combinatorial data which we call bidistance. A bidistance is a pair of functions from the edges of a bigraph to the rational numbers $\mathbb{Q}$, which satisfies certain conditions. Using a bidistance $d$ of a bigraph $B$ we can define a new bigraph $B_{d}$ with the same number of edges. The solutions of the equations for the bigraph $B$ that correspond to the bidistance $d$ are in bijection with the solutions of the equations for $B_{d}$. Then the solutions for $B$ are partitioned by the bidistances, implying the following formula for the Laman number:

From this we finally show the combinatorial recursion formula. For doing so we prove that $\operatorname{Lam}(B_{d})$ is either easy to compute or the product of two Laman numbers of bigraphs with fewer edges each. We need some more notation to state the theorem.

It can be easily seen, that if $G$ is a Laman graph, then the bigraph $(G,G)$ is pseudo-Laman. From a given bigraph we want to construct new ones with a smaller number of edges. We introduce two constructions, quotient and complement, both for usual graphs (see Figure 3) and for bigraphs.

Although the algorithm resulting from Theorem 2 has exponential complexity, it is much faster than computing the Laman number from a parametrized system of polynomial equations, even if the parameters are substituted by random values. Using our recursion formula we were able to compute Laman numbers for all Laman graphs up to 13 vertices. Furthermore, we computed Laman numbers for single graphs up to 22 vertices, which was out of reach with the previous methods. Additional information including implementations in Mathematica and in C++ can be found at www.koutschan.de/data/laman/ and https://zenodo.org/record/1245506.

The first upper bound [1] on the number of realizations of rigid graphs was derived using degree bounds from algebraic geometry. Based on the theory of distance matrices and determinantal varieties, the upper bound $\binom{2n-4}{n-2}=\Theta(4^{n}/\sqrt{n})$ is obtained, where $n$ denotes the number of vertices. This bound was improved [10] by exploiting the sparsity of the underlying polynomial systems, and it was further improved by applying additional tricks to take advantage of the sparsity and the common sub-expressions that appear in the polynomial systems [4]. A direct application of mixed volume techniques, which capture the sparsity of a polynomial system, yields a bound of $4^{n-2}$. If one also takes into account the degree of the vertices, then for a Laman graph with $k\geq 4$ degree-$2$ vertices, the number of realizations of $G$ is bounded from above by $2^{k-4}4^{n-k}$.

The first lower bounds for the number of realizations of Laman graphs were $24^{\lfloor(n-2)/4\rfloor}$ (approx. $2.21^{n}$) and $2\cdot 12^{\lfloor(n-3)/3\rfloor}$ (approx. $2.29^{n}$), which exploited a gluing process using a caterpillar, resp. fan construction [1]. Both constructions use the three-prism graph (sometimes also called Desargues graph) as a building block, which is a graph with $n=6$ vertices and $24$ realizations. More recent lower bounds are $2.30^{n}$ from [3] and $2.41^{n}$ from [7].

We derive better lower bounds on the maximal number of complex realizations of minimally rigid graphs with a prescribed number of vertices. Clearly, the number of complex realizations is an upper bound on the number of real realizations. It is known [7] that the numbers of real and complex realizations do not match in general, and it is an interesting problem to quantify this gap. On the one hand, one can construct infinite families of graphs for which the ratio between real and complex realizations tends to zero. On the other hand, there are graphs, see [3] for a nontrivial example, where real edge lengths can be found such that there exist as many real realizations as complex ones.

Using the novel algorithm presented in Section 2 we compute the exact number of realizations for graphs with a relatively small number of vertices. Then we introduce techniques to “glue” an arbitrary number of such small graphs in order to produce graphs with a high number of vertices (and edges) that preserve rigidity. The gluing process allows us to derive the number of realizations of the final graph from the number of realizations of its components, and in this way we derive a lower bound for the number of realizations in $\mathbb{C}^{2}$. Moreover, we perform extensive experiments in order to identify those small graphs that attain the maximum number of realizations and that can be the building blocks for the gluing process.