Paradoxical Mobility of $K_{3,3}$ Revisited


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.

Innsbruck, Austria
Jan Legerský
Assistant professor