Nov 20, 2019
Geometry Seminar of the Research Group Differential Geometry and Geometric Structures, TU Wien
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.
Jun 12, 2019
Geometric constraint systems: rigidity, flexibility and applications
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.
Jun 6, 2019
Conference on Geometry: Theory and Applications
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.
Mar 18, 2019
EuroCG 2019
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.
Jan 31, 2019
ARCADES - 2nd Software & Industrial Workshop
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.