2009/06/08 by Ioannis Z. Emiris, Emiris, Ioannis Z., Elias Tsigaridas +3
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Cellular Mechanics and Interactions #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Point processes and geometric inequalities
paper · pdf · doi:10.48550/arxiv.0906.1437
openalex publication_date 2009/06/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \RR2 and \RR3, where Laman graphs and 1-skeleta of convex simplicial polyhedra, respectively, admit inductive Henneberg constructions. We establish the first lower bound in \RR3 of about 2.52n, where n denotes the number of vertices. Moreover, our implementation yields upper bounds for n ≤ 10 in \RR2 and \RR3, which reduce the existing gaps, and tight bounds up to n=7 in \RR3.