@COMMENT {Autogenerated file by bib2html.pl version 0.94}
@InProceedings{etv-gd-2009,
Author = {Ioannis Z. Emiris and Elias P. Tsigaridas and
Antonios E. Varvitsiotis},
Title = {Algebraic Methods for Counting Euclidean Embeddings
of Rigid Graphs},
BookTitle = {Proc. {17th Int. Symp. on Graph Drawing (GD)}},
Series = "LNCS",
Editor = {D. Eppstein and E.R. Gansner},
Volume = 5849,
Pages = "195--200",
Publisher = "Springer Verlag",
address = "Chicago, USA",
date = "Sep",
year = 2009,
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 $\RR^2$ and $\RR^3$, where Laman graphs and
1-skeleta of convex simplicial polyhedra,
respectively, admit inductive Henneberg
constructions. We establish the first general 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$. ",
}