Rigidity of Frameworks

Abstract

A d-dimensional (bar-and-joint) framework is a pair (G; p) where G = (V;E) is a graph and p : V > Rd is a function which is called the realisation of the framework (G; p). A motion of a framework (G; p) is a continuous function P : [0; 1] x V > Rd which preserves the edge lengths for all t 2 [0; 1]. A motion is rigid if it also preserves the distances between non-adjacent pairs of vertices of G. A framework is rigid if all of its motions are rigid motions. An in nitesimal motion of a d-dimensional framework (G; p) is a function q : V > Rd such that [p(u) - p(v)] ~ [q(u) - q(v)] = 0 for all uv 2 E. An in nitesimal motion of the framework (G; p) is rigid if we have [p(u) - p(v)] . [q(u) - q(v)] = 0 also for non-adjacent pairs of vertices. A framework (G; p) is in nitesimally rigid if all of its in nitesimal motions are rigid in nitesimal motions. A d-dimensional framework (G; p) is generic if the coordinates of the positions of vertices assigned by p are algebraically independent. For generic frameworks rigidity and in nitesimal rigidity are equivalent. We construct a matrix of size |E| xd|V| for a given d-dimensional framework (G; p) as follows. The rows are indexed by the edges of G and the set of d consecutive columns corresponds to a vertex of G. The entries of a row indexed by uv 2 E contain the d coordinates of p(u) - p(v) and p(v) - p(u) in the d consecutive columns corresponding to u and v, respectively, and the remaining entries are all zeros. This matrix is the rigidity matrix of the framework (G; p) and denoted by R(G; p). Translations and rotations of a given framework (G; p) give rise to a subspace of dimension d+1 2

of the null space of R(G; p) when p(v) affinely spans Rd. Therefore we have rankR(G; p) djV j�� d+1 2

if p(v) affinely spans Rd, and the framework is in infinitesimally rigid if equality holds. We construct a matroid corresponding to the framework (G; p) from the rigidity matrix R(G; p) in which F E is independent if and only if the rows of R(G; p) indexed by F are linearly independent. This matroid is called the rigidity matroid of the framework (G; p). It is clear that any two generic realisations of G give rise to the same rigidity matroid. In this thesis we will investigate rigidity properties of some families of frameworks. We rst investigate rigidity of linearly constrained frameworks i.e., 3- dimensional bar-and-joint frameworks for which each vertex has an assigned plane to move on. Next we characterise rigidity of 2-dimensional bar-and-joint frameworks (G; p) for which three distinct vertices u; v;w 2 V (G) are mapped to the same point, that is p(u) = p(v) = p(w), and this is the only algebraic dependency of p. Then we characterise rigidity of a family of non-generic body-bar frameworks in 3-dimensions. Finally, we give an upper bound on the rank function of a d-dimensional bar-and-joint framework for 1 < d < 11.