The study of (minimally) rigid graphs is motivated by numerous applications, mostly in robotics and bioinformatics. A major open problem concerns the number of embeddings of such graphs, up to rigid motions, in Euclidean space. We capture embeddability by polynomial systems with suitable structure, so that their mixed volume, which bounds the number of common roots, to yield interesting upper bounds on the number of embeddings. We focus on $\RR^2$ and $\RR^3$, where Laman graphs and 1-skeleta of convex simplicial polyhedra, respectively, admit inductive Henneberg constructions. We establish the first lower bound in $\RR^3$ of about $2.52^n$, where $n$ denotes the number of vertices. Moreover, our implementation yields upper bounds for $n \le 10$ in $\RR^2$ and $\RR^3$, which reduce the existing gaps, and tight bounds up to $n=7$ in $\RR^3$

Additional Metadata
Keywords rigid graph, Euclidean embedding, Henneberg construction, polynomial system, lower bound, root bound, cyclohexane caterpillar
MSC Computer graphics; computational geometry (msc 68U05)
THEME Logistics (theme 3)
Publisher Springer
Editor E.R. Gasner
Series Lecture Notes in Computer Science
Conference International Symposium on Graph Drawing
Citation
Emiris, I.Z, Tsigaridas, E.P, & Varvitsiotis, A. (2009). Algebraic Methods for Counting Euclidean Embeddings of Rigid Graphs . In E.R Gasner (Ed.), Lecture notes in Computer Science. Springer.