Algebraic methods for counting Euclidean embeddings of rigid graphs

Details Algebraic methods for counting Euclidean embeddings of rigid graphs Algebraic methods for counting Euclidean embeddings of rigid graphs

2009-06-08

arxiv.org/abs/0906.1437v2

Computer Science

Computational Geometry

8 pages, 7 figures, 2 tables. To appear in Graph Drawing 2009

Scientific paper

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 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$.

Affiliated with

Also associated with

No associations

Rating

Algebraic methods for counting Euclidean embeddings of rigid graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Algebraic methods for counting Euclidean embeddings of rigid graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algebraic methods for counting Euclidean embeddings of rigid graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-231776