The Number of Realizations of a Laman Graph

Jose Capco, Matteo Gallet, Georg Grasegger, Christoph Koutschan, Niels Lubbes, Josef Schicho

Johann Radon Institute for Computational and Applied Mathematics (RICAM)
Austrian Academy of Sciences (ÖAW)

Research Institute for Symbolic Computation (RISC)
Johannes Kepler University Linz (JKU)


Laman graph with 18 vertices

Abstract

Laman graphs model planar frameworks that are rigid for a general choice of distances between the vertices. There are finitely many ways, up to isometries, to realize a Laman graph in the plane. Such realizations can be seen as solutions of systems of quadratic equations prescribing the distances between pairs of points. Using ideas from algebraic and tropical geometry, we provide a recursion formula for the number of complex solutions of such systems.

Material

Algorithm

The algorithm is sketched in our working notes. Here we show an example of a computation tree; due to the complexity of the algorithm, we use a very simple example, namely the bigraph consisting of two triangles. The result is 2, which is indeed the Laman number of the triangle. By L(G,H) we denote the Laman number of the bigraph (G,H), and a graph here is given by its edges: each row of the n×2 matrix contains two vertices that are connected by an edge.

Computation tree for the bigraph consisting of two triangles
(see the full size image)

Real Embeddings of the Three-Prism Graph

An interesting question is whether one can find as many real embeddings of a Laman graph as is given by its Laman number; the latter counts the number of its complex embeddings. For the three-prism graph we found an assignment of the edge lengths $$z_{1,2}=2,z_{1,3}=2,z_{2,3}=2,z_{1,4}=\tfrac{7}{4},z_{3,6}=\tfrac{27}{10},$$ $$z_{2,5}=\tfrac{197}{100},z_{4,5}=\tfrac{11}{5},z_{4,6}=\tfrac{29}{10},z_{5,6}=\tfrac{43}{20}$$ such that all its 24 embeddings are real. Below we show 12 of them, the remaining 12 ones are obtained by reflection across the vertical axis.

Real Embeddings of the Three-Prism Graph
(see the full size image)

Remarkably enough, when building a mechanical device with the above lengths (see the figure below), all 12 configurations can be reached without disassembling the linkage. This is shown in the animation.

Real Embedding of the Three-Prism Graph (see the animation)

Software

The algorithms described in our paper have been implemented in the computer algebra system Mathematica and in C++.
Contact: Visitors: