Algebraic Methods for Counting Euclidean Embeddings of Rigid GraphsEmiris, Ioannis Z. and Tsigaridas, Elias P. and Varvitsiotis, Antonios E. (2010) Algebraic Methods for Counting Euclidean Embeddings of Rigid Graphs. In: Graph Drawing 17th International Symposium, GD 2009, September 2225, 2009 , pp. 195200(Official URL: http://dx.doi.org/10.1007/9783642118050_19). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783642118050_19
AbstractThe 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 R2 and R3 , where Laman graphs and 1skeleta of convex simplicial polyhedra, respectively, admit inductive Henneberg constructions. We establish the ﬁrst general lower bound in R3 of about 2.52n , where n denotes the number of vertices. Moreover, our implementation yields upper bounds for n ≤ 10 in R2 and R3 , which reduce the existing gaps, and tight bounds up to n = 7 in R3 . Keywords: Rigid graph, Euclidean embedding, Henneberg construction, polynomial system, root bound, cyclohexane caterpillar.
Actions (login required)
