Abstract
Rigidity Theory studies realizations of a graph in the plane or space satisfying constraints given by edge lengths. A realization is compatible with a given edge labeling of the graph if the Euclidean distance of any two adjacent vertices is equal to the label of this edge. We say that two realizations are congruent if they differ only by a rigid transformation. Labelings with infinitely many non-congruent compatible realizations are called flexible, whereas if the number of non-congruent compatible realizations is positive and finite, they are called rigid.
A graph is called generically rigid if the labeling induced by a generic realization is rigid. Nevertheless, it still may admit a non-generic flexible labeling. This is the main focus of the thesis — to study non-generic flexible labelings. We show that a flexible labeling exists if and only if there is a so called NAC-coloring. A NAC-coloring is a coloring of the edges in red and blue such that for every cycle, either all edges of the cycle have the same color, or there are at least two blue and two red edges.
Since nonadjacent vertices might coincide in realizations compatible with a flexible labeling coming from a NAC-coloring, we restrict ourselves to flexible labelings that are proper, i.e., they have infinitely many vertex-injective realizations. We provide a necessary combinatorial condition on the existence of a proper flexible labeling, which is based on all NAC-colorings of the graph. By various constructions of proper flexible labelings, we prove that this condition is also sufficient for all graphs up to eight vertices, but not in general.
Some tools for studying possible families of proper flexible labelings of a generically rigid graph are presented. The concept of NAC-colorings is used again, since some NAC-colorings are active for a specific motion of the graph. Active NAC-colorings provide algebraic constraints for the edge lengths. Moreover, we describe a method determining possible active NAC-colorings based on restrictions to 4-cycle subgraphs. We apply the tools to classify all proper flexible labelings of a certain generically rigid graph with seven vertices.
Besides flexible labelings, we study also rigid labelings.
The realizations compatible with a rigid labeling are solutions
of an algebraic system, which are in general complex.
For some generically rigid graphs,
we have found labelings with many real solutions
using sampling around unit distance lengths.
We also describe a method based on coupler curves which gives rigid labelings
with a high number of real realizations for some minimally
rigid graphs in 3-space.
