## Rigidity of Frameworks

##### Publisher

##### Metadata

Show full item record##### 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.

##### Authors

Guler, Hakan##### Collections

- Theses [2565]