Realizations of Rigid Graphs

Christoph Koutschan
(Johann Radon Institute for Computational and Applied Mathematics (RICAM), 4040 Linz, Austria)

A minimally rigid graph, also called Laman graph, models a planar framework which is rigid for a general choice of distances between its vertices. In other words, there are finitely many ways, up to isometries, to realize such a graph in the plane. Using ideas from algebraic and tropical geometry, we derive a recursive formula for the number of such realizations. Combining computational results with the construction of new rigid graphs via gluing techniques, we can give a new lower bound on the maximal possible number of realizations for graphs with a given number of vertices.

Invited Lecture in Predrag Janičić and Zoltán Kovács: Proceedings of the 13th International Conference on Automated Deduction in Geometry (ADG 2021), Hagenberg, Austria/virtual, September 15-17, 2021, Electronic Proceedings in Theoretical Computer Science 352, pp. 4–13.
Published: 30th December 2021.

ArXived at: http://dx.doi.org/10.4204/EPTCS.352.2 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org