Abstract
In 1899, Dixon provided two classes of edge lengths for the bipartite graph K3,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 K3,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.
