Flexibility of frameworks using edge colorings

Abstract

A framework, which is a graph together with a realization of its vertices in the plane such that adjacent vertices are mapped to distinct points, is called flexible if it can be continuously non-trivially deformed while preserving the edge lengths, i.e., the distances between adjacent vertices; otherwise it is rigid.
It is well known that for a fixed graph being flexible/rigid is a generic property in the space of realizations. But even if a graph is generically rigid, it might admit non-generic flexible realizations. For instance, the complete bipartite graph on 3+3 vertices, which is generically rigid, has two families of flexible realizations given by Dixon.
A few years ago, we showed that a graph admits a (non-generic) flexible realization if and only if its edges can be colored surjectively by two colors so that each cycle is either monochromatic, or both colors occur at least twice. Such colorings are called NAC-colorings. In this talk, we focus on some contexts in which NAC-colorings have been considered: they characterize the existence of flexible realizations also for infinite graphs, their subclass is related to the flexibility on sphere and symmetric NAC-colorings determine the existence of flexes preserving rotational symmetry.
Moreover, for a class of frameworks consisting of triangles and parallelograms, the flexibility of a given framework is determined by the existence of a certain NAC-coloring. In this case, more detailed information about flexibility of a given framework can be obtained using the classes of an equivalence relation defined on the edge set of the graph. We illustrate the results on frameworks obtained from Penrose tilings and periodic tessellations by regular polygons.