Talks

A well known result of Bolker and Crapo determines how to make a grid of squares rigid by bracing, i.e., adding diagonals. The result had been generalized to bracing frameworks consisting of parallelograms with richer combinatorial structure. In this talk we focus on frameworks that besides (braced) parallelograms contain also triangles that do not originate from bracing. We define a certain equivalence on the edge set of the graph to show that such a framework is flexible if and only if it is infinitesimally flexible if and only if it has at least two equivalence classes.

A framework, which is a (possibly infinite) graph together with a realization of its vertices in the plane, is called flexible if it can be continuously deformed while preserving the distances between adjacent vertices. The existence of a flexible framework for a given graph is characterised by the existence of a so called NAC-coloring — a surjective edge coloring by red and blue such that each cycle is either monochromatic, or contains at least two red and two blue edges. In this talk, we focus on infinite frameworks obtained as 1-skeleta of parallelogram tilings. We brace some of the parallelograms, namely, they are not allowed to change their shape during a flex. We show that such a structure is flexible if and only if the graph admits a special type of NAC-coloring, called cartesian. Moreover, if this framework is n-fold rotationally symmetric, we can again decide its flexibility by the existence a cartesian NAC-coloring invariant under the symmetry. In particular, we can apply these results to frameworks obtained from (5-fold symmetric) Penrose tilings.

It is known that all convex polyhedra are rigid as well as almost all simply connected ones. Hence, it is a non-trivial task to provide a flexible polyhedron. However, flexible polyhedra exist, for instance Bricard’s octahedra or Steffen’s polyhedron. We provide a necessary condition on the flexibility of a polyhedron, namely, if a polyhedron flexes, then there is a cycle of edges with a sign assignment such that the signed sum of the edge lengths is zero. Our result is a generalization of the analogous statement for suspensions. This is a joint work with Matteo Gallet, Georg Grasegger and Josef Schicho.

A planar framework, which is a graph together with a map of its vertices to the plane, is flexible if it allows a continuous deformation preserving the distances between adjacent vertices. It has been shown recently that a finite graph admits a flexible framework if and only if it has a so called NAC-coloring, which is an edge coloring with a condition on cycles. We extend this result to the case of frameworks with countable vertex sets. This is a joint work with M. Gallet and J. Schicho

A rectangle in the plane can be continuously deformed preserving its edge lengths, but adding a diagonal brace prevents such a deformation. Choices of braces making a grid of squares infinitesimally rigid were characterized earlier using a bipartite graph constructed from the braced framework. We exploit the concept of NAC-colorings used to characterize the existence of flexible frameworks. In this way we give the results on bracing for a larger class of frameworks with every 4-cycle forming a parallelogram. This is a joint work with Georg Grasegger.

In 1899, Dixon provided two classes of edge lengths for the bipartite graph $K_{3,3}$ such that there are infinitely many realizations in the plane with the distances between adjacent vertices satisfying the edge lengths, counted modulo translations and rotations. More than a hundred years later, Walter and Husty proved using resultants that these are the only possible motions of $K_{3,3}$. We exploit the concept of NAC-colorings of a graph – edge colorings with two colors such that every cycle is either monochromatic or there are at least two edges of each color. A certain subset of the NAC-colorings is active in a particular motion. We present a method to obtain possible sets of active NAC-colorings for graphs with many 4-cycles and how they yield necessary conditions on edge lengths. This allows to give a new proof of the result of Walter and Husty and classify all motions of another 7-vertex graph. This is a joint work with Georg Grasegger and Josef Schicho.

Laman graphs are known to be minimally rigid in the plane, but they might admit non-generic edge lengths such that there are infinitely many non-congruent vertex-injective realizations. In this talk we present some tools for determing families of such edge lengths. Our methods are based on NAC-colorings, whose existence characterizes the existence of edge lengths with infinitely many non-congruent realizations without the injectivity requirement. We exploit the fact that a subset of active NAC-colorings can be assigned to a particular motion of a graph. We can determine possible active AC-colorings if there are enough 4-cycle subgraphs. Moreover, certain active NAC-colorings impose some algebraic constraints on edge lengths. This allows to give an alternative proof of the result of Walter and Husty stating that the two motions of the complete bipartite graph on 3+3 vertices proposed by Dixon are the only possible ones. Next, we classify the motions of another Laman graph. This is a joint work with Georg Grasegger and Josef Schicho.

In 1899, Dixon provided two classes of edge lengths for the bipartite graph $K_{3,3}$ such that there are infinitely many realizations in the plane with the distances between adjacent vertices satisfying the edge lengths, counted modulo translations and rotations. The first construction places the vertices on two perpendicular lines so that the vertices of each partition are collinear. In the second one, the vertices of each partition are at vertices of two rectangles respectively. These rectangles have the same intersection of diagonals and their sides are parallel/orthogonal to each other. More than a hundred years later, Walter and Husty proved using resultants that these are the only possible motions of $K_{3,3}$. In this talk, we give another proof of this result based on restrictions of a motion of $K_{3,3}$ to 4-cycle subgraphs and the concept of NAC-colorings – edge colorings with two colors such that every cycle is either monochromatic or there are at least two edges of each color. A certain subset of the NAC-colorings of $K_{3,3}$ can be assigned to a particular motion and gives necessary conditions on the edge lengths. This is a joint work with Georg Grasegger and Josef Schicho.

A graph is called movable if there exists a proper flexible labeling, i.e., an edge labeling such that there are infinitely many injective realizations of the graph in the plane, counted modulo rigid motions, such that the distances between adjacent vertices equal the labels. Of special interest is the class of generically rigid graphs that are movable due to a non-generic proper flexible labeling. We introduce two methods for investigating possible proper flexible labelings. The first one is based on restrictions to 4-cycles and gives an easy classification of all but one non-bipartite 6 and 7-vertex graphs in the class. Using our second method, we prove that every proper flexible labeling of this one graph forces the vertices in its only 3-cycle to be collinear. This is joint work with Georg Grasegger and Josef Schicho.

In this talk, a SageMath package for investigating rigidity and flexibility of graphs is presented. The main focus is on the combinatorial properties related to NAC-colorings of a graph, since they provide some necessary/sufficient conditions on movability of the graph.

Given a graph, we ask whether it is possible to find a flexible labeling, namely, edge lengths such that there are infinitely many compatible realizations, modulo rigid motions. Even if a graph is generically rigid, the non-generic edge lengths may still be flexible. In case realizations are not required to be injective, the graphs with a flexible labeling are characterized by the existence of a special edge coloring that is called NAC-coloring. In this talk we focus on graphs and labelings allowing infinitely many injective realizations. We provide a necessary condition on the movability of a graph that is also based on the NAC-colorings of the graph. We show that the condition is also sufficient for graphs with at most 8 vertices, which is not true in general. This is joint work with Georg Grasegger and Josef Schicho.

Given a graph, we ask whether it is possible to find a flexible labelling, namely, edge lengths such that there are infinitely many compatible realizations, modulo rigid motions. Even if a graph is generically rigid, then non-generic edge lengths may still be flexible. A classical construction by A. Dixon from 1899 works for all bipartite graphs. In this talk, we give a combinatorial criterion for the existence of a flexible labelling. This is joint work with Georg Grasegger and Josef Schicho.

We present recent results on bounds for the number of realizations of minimally rigid graphs in plane and space. We consider complex solutions of the corresponding algebraic systems and give asymptotic bounds for the maximal number of realizations. Furthermore, we introduce a method for specifying edge lengths allowing many real solutions.

The number of embeddings of minimally rigid graphs in $\mathbb{R}^D$ is (by definition) finite, modulo rigid transformations, for every generic choice of edge lengths. Even though various approaches have been proposed to compute it, the gap between upper and lower bounds is still enormous. Specific values and its asymptotic behavior are major and fascinating open problems in rigidity theory. Our work considers the maximal number of real embeddings of minimally rigid graphs in $\mathbb{R}^3$. We modify a commonly used parametric semi-algebraic formulation that exploits the Cayley-Menger determinant to minimize the a priori number of complex embeddings, where the parameters correspond to edge lengths. To cope with the huge dimension of the parameter space and find specializations of the parameters that maximize the number of real embeddings, we introduce a method based on coupler curves that makes the sampling feasible for spatial minimally rigid graphs. Our methodology results in the first full classification of the number of real embeddings of graphs with 7 vertices in $\mathbb{R}^3$, which was the smallest open case. Building on this and certain 8-vertex graphs, we improve the previously known general lower bound on the maximum number of real embeddings in $\mathbb{R}^3$.