The characterization of rigid graphs in $\R^d$ is known only in the low dimensional cases ($d=1,2$) and is a major open problem in higher dimensions. In this note we consider the other extreme case when $d$ is close to $n$, the number of vertices of the graph. It turns out that there is a fairly simple characterization as long as $n-d$ is at most four. We also characterize globally rigid graphs in this range.
Bibtex entry:
@techreport{egres-20-01,
AUTHOR | = | {Jord{\'a}n, Tibor}, |
TITLE | = | {A note on generic rigidity of graphs in higher dimension}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2020}, |
NUMBER | = | {TR-2020-01} |