Mixed Volume and Distance Geometry Techniques for Counting Euclidean Embeddings of Rigid Graphs

Ioannis Z. Emiris (), Elias P. Tsigaridas () and Antonios Varvitsiotis ()
Additional contact information
Ioannis Z. Emiris: University of Athens
Elias P. Tsigaridas: INRIA Paris-Rocquencourt
Antonios Varvitsiotis: Centrum Wiskunde & Informatica (CWI)

Chapter Chapter 2 in Distance Geometry, 2013, pp 23-45 from Springer

Abstract: Abstract A graph G is called generically minimally rigid in ℝ d if, for any choice of sufficiently generic edge lengths, it can be embedded in ℝ d in a finite number of distinct ways, modulo rigid transformations. Here, we deal with the problem of determining tight bounds on the number of such embeddings, as a function of the number of vertices. The study of rigid graphs is motivated by numerous applications, mostly in robotics, bioinformatics, sensor networks, and architecture. We capture embeddability by polynomial systems with suitable structure so that their mixed volume, which bounds the number of common roots, yields interesting upper bounds on the number of embeddings. We explore different polynomial formulations so as to reduce the corresponding mixed volume, namely by introducing new variables that remove certain spurious roots and by applying the theory of distance geometry. We focus on $${\mathbb{R}}^{2}$$ and $${\mathbb{R}}^{3}$$ , where Laman graphs and 1-skeleta (or edge graphs) of convex simplicial polyhedra, respectively, admit inductive Henneberg constructions. Our implementation yields upper bounds for $$n \leq 10$$ in $${\mathbb{R}}^{2}$$ and $${\mathbb{R}}^{3}$$ , which reduce the existing gaps and lead to tight bounds for $$n \leq 7$$ in both $${\mathbb{R}}^{2}$$ and $${\mathbb{R}}^{3}$$ ; in particular, we describe the recent settlement of the case of Laman graphs with seven vertices. Our approach also yields a new upper bound for Laman graphs with eight vertices, which is conjectured to be tight. We also establish the first lower bound in $${\mathbb{R}}^{3}$$ of about 2. 52 n , where n denotes the number of vertices.

Keywords: Rigid graph; Laman graph; Euclidean embedding; Henneberg construction; Polynomial system; Mixed volume; Cayley–Menger matrix; Cyclohexane caterpillar. (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4614-5128-0_2

Ordering information: This item can be ordered from
http://www.springer.com/9781461451280

DOI: 10.1007/978-1-4614-5128-0_2

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().