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. In the paper Graphs with Flexible Labelings, we have shown that existence of a 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.

Nevertheless, even if a NAC-coloring exists, the motion might be degenerated - the compatible realizations are not necessarily injective. We call a graph movable, if there exists a proper flexible labeling, i.e., it has infinitely many compatible injective realizations. The concept of constant distance closure of a graph is introduced in the paper Graphs with Flexible Labelings allowing Injective Realizations. It is the graph augmented with extra edges based on NAC-colorings. We have proved 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. For some graphs, a proper flexible labeling can be constructed based on certain embedding in the space related with two NAC-colorings: animations of motions with 2 active NAC-colorings

Jan Legerský
PhD Student


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

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