Published in:
European Journal of Combinatorics, Volume 94, 2021. DOI link
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 egres.elte.hu}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2019}, |
NUMBER | = | {TR-2019-13} |