Counting Euclidean embeddings of rigid graphs

MaRDI QIDQ6248833zbMATH OpenFDO

Authors Ioannis Z. Emiris, Ioannis Psarros

Publication date 6 February 2014

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.

This page was built for publication: Counting Euclidean embeddings of rigid graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6248833)