TR-2019-13

Rigid realizations of graphs with few locations in the plane

Csaba Király



Abstract

Adiprasito and Nevo (2018) proved that there exists a set of 76 points in $\R^3$ such that every triangulated planar graph has an infinitesimally rigid realization in which each vertex is mapped to a point in this set.
 
In this paper we show that there exists a set $A$ of 26 points in the plane such that every planar graph which is generically rigid in $\R^2$ has an infinitesimally rigid realization in which each vertex is mapped to a point in this set.
 
It is known that a similar result, with a set of constant size, does not hold for the family of all generically rigid graphs in $R^d$, $d\geq 2$. We show that for every positive integer $n$ there is a set of $c(\sqrt{n})$ points in the plane, for some constant $c$, such that every generically rigid graph in $R^2$ has an infinitesimally rigid realization on this set. This bound is best possible.


Bibtex entry:

@techreport{egres-19-13,
AUTHOR = {Kir{\'a}ly, Csaba},
TITLE = {Rigid realizations of graphs with few locations in the plane},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2019},
NUMBER = {TR-2019-13}
}


Last modification: 16.10.2019. Please email your comments to Tamás Király!