Paradoxical flexibility of frameworks is a joint project between RICAM in Linz and FIT, CTU in Prague evaluated on the Lead Agency principle (FWF). The Austrian part of the project is funded by FWF Austrian Science Fund as International project I 6233 (Jan 2023 – Dec 2025) led by Georg Grasegger. The Czech part is funded by the Czech Science Foundation (GAČR) as project 22-04381L (Oct 2022– Sept 2025) led by Jan Legerský.

Paradoxical motions occur when some structure that is expected to be rigid turns out to be flexible for some very particular cases. As a basic real world structure we may think of truss constructions like bridges, towers or scaffolds. We consider more general but also more abstract constructions. We take a set of rotational joints that are connected by some bars with fixed lengths. When we build a triangle out of them and place it in the plane, then the only way to move it is to rotate or translate the whole triangle, or to do a combination of those. Such an object we call rigid. When we take four joints with four bars connected in a cycle, then we get something flexible, because the object allows a continuous deformation preserving the length of the bars.

Rigid framework	Flexible framework

If we forget about the lengths of the bars we get a graph. This is a set of vertices (representing the joints) and edges (representing the bars). It turns out that in general the structure of a graph already tells a lot about its rigidity properties. But many graphs yield a rigid object for almost all choices of edge lengths but just for some very particular ones they turn out to result in a flexible one. In this project we investigate these special instances. It is known that flexible situations can be related to special colorings of the edges. However, it is complicated to find such colorings. Part of the project therefore deals with speeding up this computation.

Furthermore we investigate symmetric graphs and paradoxical motions preserving symmetry. While there is a connection between colorings and rotationally symmetric motions, no such result is yet known for other symmetries.

Also in other applications rigidity plays a role. For instance in sensor networks the measurements of distances can be used for determining positions of sensors. But this can only be done if for the underlying graph there is only one placement up to rotations and translations that gives the measured lengths. But also such graphs can have paradoxical flexibility, which would make it impossible to detect the positions. Finally, there are graphs that are generically flexible but certain placements allow additional mobility. We can also add different constraints on the graph or the motions. In all such cases paradoxical flexibility is interesting and is investigated in this project.

More mathematically

We consider a framework which is graph $G=(V_G, E_G)$ together with a realization in the plane – a map $\rho : V_G \rightarrow \mathbb{R}^2$ such that adjacent vertices are mapped to distinct points. Two frameworks $(G,\rho)$ and $(G,\rho’)$ are called equivalent if $$||\rho(u)-\rho(v)||=||\rho’(u)-\rho’(v)||$$ for all $uv \in E_G$ and congruent if the equation above holds for all $u,v\in V_G$. A flex of framework $(G,\rho)$ is a continuous mapping $t \mapsto \rho_t$ from the interval $[0,1)$ to the set of realizations of $G$ such that $\rho_0=\rho$ and $\rho_t$ is equivalent to $\rho$ for all $t \in (0,1)$. The flex is called non-trivial if $\rho_t$ is non-congruent to $\rho$ for all $t \in (0,1)$. If framework $(G,\rho)$ has a non-trivial flex, it is called flexible, otherwise rigid.

It is well-known that being rigid or flexible is a generic property in the space of all realizations of a fixed graph. Hence, we define a graph to be generically rigid if its generic realizations are rigid. However, a generically rigid graph can admit a flexible realization. This is what we mean by paradoxical flexibility and is investigated in this project.

The existence of a flexible realization is characterized by the existence of a NAC-coloring of the graph: a surjective edge coloring by red and blue such that every cycle is either monochromatic, or contains at least two blue and two red edges. An example of a NAC-coloring is below (refresh the page to start the animation again).

It is known that the existence of a NAC-coloring is an NP-complete problem, but we want to improve the naive approach of listing all NAC-colorings to a faster implementation. NAC-colorings play nicely if one forces the realizations in a non-trivial flex to be rotationally symmetric, in particular they are invariant under the symmetry, but the extension to other symmetries like reflection or dihedral is not straightforward and shall be investigated.

Graphs that are important in sensor networks to determine the positions of sensors based on the measurements on mutual distances are globally rigid graphs – a generic realization has no non-congruent equivalent realization. Such graphs still can admit a flexible realization, hence, we would like to be able to describe all their flexible realizations to make sure that the solution of the localization problem is unique modulo rotations and translations if this set is avoided.

NAC-colorings deal with one-parametric families of realizations. We would like to study also frameworks that have more degrees of freedom than expected. One can also consider rigidity of other realizations than in the plane or various other constraints and the possible paradoxically flexible instances. One of the approaches to deal with these questions is to formulate a problem as a polynomial system and to use tools from algebraic geometry and computer algebra to study it.