*Joint work with Sean Dewar, Georg Grasegger and Josef Schicho*

We are interested in realizations of graphs in the plane satisfying constraints given by a labeling of edges by positive real numbers.
A realization is compatible with the labeling if the distance between every two adjacent vertices equals the label.
The labeling is called *(proper) flexible* if there are infinitely many compatible (injective) realizations modulo translations and rotations.

It is well-known, due to Geiringer-Pollaczek and Laman, that the labeling induced by a generic realization of a graph is flexible if and only if the graph is not spanned by a *Laman graph*,
where a graph $G=(V_G,E_G)$ is called Laman if

- $|E_G|=2|V_G|-3$, and
- $|E_H|\leq2|V_H|-3$ for every subgraph $H$ of $G$ such that $|V_H|\geq 2$.

We focused on the non-generic cases in the paper Graphs with Flexible Labelings.
Namely, we have shown that the existence of a (non-generic) flexible labeling
is equivalent to the existence of a *NAC-coloring* - a coloring of edges by red and blue such that
every cycle is either monochromatic, or it contains at least two red and two blue edges (see animations).

## Proper flexible labelings

Even if a NAC-coloring exists, the motion constructed from it might be degenerate - the compatible realizations are not necessarily vertex-injective. This happens for instance for this NAC-coloring:

We call a graph *movable*, if there exists a *proper* flexible labeling.
A known example of a movable graph is $K_{4,4}$, which has two different motions.

The concept of *constant distance closure* of a graph $G$ is introduced in the paper Graphs with Flexible Labelings allowing Injective Realizations.
It is obtained from the graph $G$ by adding extra edges using NAC-colorings.
We have proven that if a graph is movable, then its constant distance closure is not a complete graph.
Moreover, up to 8 vertices, this necessary condition is also sufficient.

The proof of sufficiency is based on the known constructions of proper flexible labeling and some new ones: for instance, a proper flexible labeling can be constructed based on certain embedding in $\mathbb{R}^3$ related with two NAC-colorings (see details and animations). For some graphs, we construct a proper flexible labeling from motions of subgraphs or ad hoc.

## Classification of motions

Given a motion of a graph, some of the NAC-colorings of the graph are so-called *active* for this motion.
The paper On the Classification of Motions of Paradoxically Movable Graphs describes how
an active NAC-coloring of a graph with a spanning Laman subgraph enforces an algebraic condition on edge lengths.
Moreover, we describe a procedure allowing us to obtain all possible sets of active NAC-colorings.
This gives a new proof of the classification of motions of $K_{3,3}$.
We also classify all proper flexible labelings of the graph displayed above (see animations).

## $n$-fold rotational symmetry

Let $G$ be a graph with a cyclic subgroup of order $n$ of the automorphism group such that the vertices having the orbit smaller than $n$ form an independent set. The construction of a motion from a NAC-coloring of $G$ can be adjusted so that each realization of the motion is $n-fold rotationally symmetric, provided that the NAC-coloring satisfies some extra conditions related to the symmetry. It holds also the other way around: if there is such a motion, then there is a NAC-coloring satisfying the properties. These results can be found in the papers Rotational symmetric flexible placements of graphs and Flexible placements of graphs with rotational symmetry

## FlexRiLoG

The used concepts are implemented in the SageMath package `FlexRiLoG`

:
The latest version can be found on GitHub.
The basic functionality of the package is described in the paper FlexRiLoG – A SageMath Package for Motions of Graphs, see also the Jupyter notebook version of the paper
and the documentation.