Rigid Graphs that are Movable

Abstract

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.

Publication
The 35th European Workshop on Computational Geometry (EuroCG 2019)
Date
Next
Previous