Algebraic Methods for Counting Euclidean Embeddings of Rigid Graphs

Emiris, 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 22-25, 2009, Chicago, IL, USA , pp. 195-200 (Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_19).

Full text not available from this repository.

Abstract

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 R2 and R3 , where Laman graphs and 1-skeleta of convex simplicial polyhedra, respectively, admit inductive Henneberg constructions. We establish the first 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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-11805-0_19
Classifications:M Methods > M.100 Algebraic
G Algorithms and Complexity > G.560 Geometry
ID Code:1084

Repository Staff Only: item control page

References

Bernstein, D.N.: The number of roots of a system of equations. Fun. Anal. Pril. 9, 1–4 (1975)

Borcea, C., Streinu, I.: The number of embeddings of minimally rigid graphs. Discrete Comp. Geometry 31(2), 287–303 (2004)

Bowen, R., Fisk, S.: Generation of triangulations of the sphere. Math. of Computation 21(98), 250–252 (1967)

Emiris, I.Z., Mourrain, B.: Computer algebra methods for studying and computing molecular conformations. Algorithmica, Special Issue 25, 372–402 (1999)

Emiris, I.Z., Varvitsiotis, A.: Counting the number of embeddings of minimally rigid graphs. In: Proc. Europ. Workshop Comput. Geometry, Brussels (2009)

Gluck, H.: Almost all simply connected closed surfaces are rigid. Lect. Notes in Math. 438, 225–240 (1975)

Steffens, R., Theobald, T.: Mixed volume techniques for embeddings of Laman graphs. In: Proc. Europ. Workshop Comput. Geometry, Nancy, France, pp. 25–28 (2008); Final version accepted in Comp. Geom: Theory & Appl., Special Issue

Walter, D., Husty, M.: On a 9-bar linkage, its possible configurations and conditions for paradoxical mobility. In: IFToMM Congress, Besancon, France (2007)

Wunderlich, W.: Gefärlice Annahmen der Trilateration und bewegliche Fachwerke a I. Zeitschrift für Angewandte Mathematik und Mechanik 57, 297–304 (1977) u