On the Classification of Motions of Paradoxically Movable Graphs


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.

Wien, Austria
Jan Legerský
PostDoc and Assistant Lecturer