Movable Graphs

Joint work with Georg Grasegger and Josef Schicho

We are interested in realizations of graphs in the plane satisfying the 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 flexible if there are infinitely many compatible realizations modulo translations and rotations.

It is well-known, due to Geiringer-Pollaczek and Laman, that a generic labeling 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$.

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

Nevertheless, even if a NAC-coloring exists, the motion might be degenerated - the compatible realizations are not necessarily injective. This happens for instance for this NAC-coloring: Example of NAC-coloring

We call a graph movable, if there exists a proper flexible labeling, i.e., it has infinitely many compatible injective realizations. By “injective”, we mean that no two vertices are mapped to a same point. 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.


. Graphs with Flexible Labelings allowing Injective Realizations. submitted, 2018.

Preprint Project Slides

. Graphs with Flexible Labelings. Journal of Discrete and Computational Geometry, 2018.

Preprint PDF Project Slides DOI


Graphs with flexible labelings allowing injective realizations
Sep 27, 2018
Graphs with flexible labelings
Jun 6, 2018