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.
