Counting Euclidean embeddings of rigid graphs

Abstract

A graph is called (generically) rigid in ${\mathbb{R}}^d$ if, for any choice of sufficiently generic edge lengths, it can be embedded in ${\mathbb{R}}^d$ in a finite number of distinct ways, modulo rigid transformations. Here we deal with the problem of determining the maximum number of planar Euclidean embeddings as a function of the number of the vertices. We obtain polynomial systems which totally capture the structure of a given graph, by exploiting distance geometry theory. Consequently, counting the number of Euclidean embeddings of a given rigid graph, reduces to the problem of counting roots of the corresponding polynomial system.

10 pages, 5 figures

References in corpus (2)

• Point Configurations and Cayley-Menger Varieties
• An upper bound on Euclidean embeddings of rigid graphs with 8 vertices