TR-2004-11

Rigid realizations of graphs on small grids

Zsolt Fekete, Tibor Jordán

Published in:
Computational Geometry, Vol. 32, Issue 3 216-222, 2005.



Abstract

A framework (G,p) is a graph G=(V,E) and a mapping p: V \to R2. We prove that if (G,p) is an infinitesimally rigid framework then there is an infinitesimally rigid framework (G,q) for which the points q(v), v \in V(G), are distinct points of the k * k grid, where k=\lceil {\sqrt{|V|-1}}\rceil+9. We also show that such a framework on G can be constructed in O(|V|3) time.


Bibtex entry:

@techreport{egres-04-11,
AUTHOR = {Fekete, Zsolt and Jord{\'a}n, Tibor},
TITLE = {Rigid realizations of graphs on small grids},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2004},
NUMBER = {TR-2004-11}
}


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