Elias' Article

Algebraic Methods for Counting Euclidean Embeddings of Rigid Graphs.
Ioannis Z. Emiris, Elias P. Tsigaridas, and Antonios E. Varvitsiotis.
In Proc. 17th Int. Symp. on Graph Drawing (GD), pp. 195–200, LNCS 5849, Springer Verlag, Chicago, USA, 2009.

• Home
• Research
• Teaching
• Contact

Files:

[PDF] 116.5kB  [gzipped postscript] 138.8kB  

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 łe 10$ in $\RR^2$ and $\RR^3$, which reduce the existing gaps, and tight bounds up to $n=7$ in $\RR^3$.

@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$.  ",
}

Generated by bib2html.pl (written by Patrick Riley , modified by Elias ) on Wed Oct 23, 2019 21:41:02