Movable Graphs

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: Example of 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: DOI 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.

Avatar
Jan Legerský
PostDoc and Assistant Lecturer

Publications

. On the Classification of Motions of Paradoxically Movable Graphs. Journal of Computational Geometry, 2020.

Preprint Code Project DOI

. FlexRiLoG – A SageMath Package for Motions of Graphs. Mathematical Software – ICMS 2020. Lecture Notes in Computer Science, 2020.

Preprint Code Project Interactive Jupyter notebook DOI

. Computing Animations of Linkages with Rotational Symmetry (Media Exposition). 36th International Symposium on Computational Geometry (SoCG 2020), 2020.

PDF Code Project Video DOI Interactive Jupyter Notebook

. Graphs with Flexible Labelings allowing Injective Realizations. Discrete Mathematics, 2020.

Preprint Code Project Slides DOI

. Flexible placements of graphs with rotational symmetry. submitted, 2020.

Preprint Project

. Rotational symmetric flexible placements of graphs. EuroCG, 2020.

PDF Project Video

. Graphs with Flexible Labelings. Discrete and Computational Geometry, 2019.

Preprint PDF Project Slides DOI

. Animated Motions of Exceptional Flexible Instances of Generically Rigid Graphs. Proceedings of Bridges 2019: Mathematics, Art, Music, Architecture, Education, Culture, 2019.

PDF Dataset Project DOI

. Rigid Graphs that are Movable. EuroCG, 2019.

PDF Project Slides

Talks

On the Classification of Motions of Paradoxically Movable Graphs
Nov 20, 2019
On the Classification of Motions of Laman Graphs
Jun 12, 2019
Paradoxical Mobility of $K_{3,3}$ Revisited
Jun 6, 2019
Rigidity and Flexibility of Graphs in SageMath
Jan 31, 2019
Graphs with flexible labelings allowing injective realizations
Sep 27, 2018
Graphs with flexible labelings
Jun 6, 2018
Next
Previous