This tutorial gives a short introduction to polymake's feature for treating frameworks and rigidity. The text contains commands to be given to the polymake system (preceded by a '>') along with the output. Commands and output are displayed in typewriter type. The tutorial deals only with two dimensional examples but the analysis works similarly in arbitrary dimension. The visualization is works only in dimensions two and three.

How to create a Framework

To create a FRAMEWORK you have to specify a GRAPH and points in homogeneous coordinates and use the framework client to combine them. So you create a file input.poly containing:

GRAPH {1 3} {0 2} {1 3} {0 2} HOM_COORDS 1 0 0 1 2 3 1 0 2 1 -2 3

To create the framework you have to call the framework client:

> framework my_framework.poly input.poly GRAPH HOM_COORDS

Now you have a FRAMEWORK object contained in the file my_framework.poly. To get the polymake representation of a framework type:

> polymake my_framework.poly FRAMEWORK

and polymake returns a graph with node attribute. The node attribute contains the coordinates of the node followed by the neighbors of the node

FRAMEWORK (<0 0> {1 3}) (<2 3> {0 2}) (<0 2> {1 3}) (<-2 3> {0 2})

Rigidity and Visualization

my_framework

The basis of all the rigidity analysis is the RIGIDITY_MATRIX. It is a matrix with N_EDGES × (N_NODES * DIM):

> polymake my_framework.poly RIGIDITY_MATRIX RIGIDITY_MATRIX -2 -3 2 3 0 0 0 0 0 0 2 1 -2 -1 0 0 2 -3 0 0 0 0 -2 3 0 0 0 0 2 -1 -2 1

To visualize the framework just use

> polymake my_framework.poly VISUAL

You may add many additional feature to the visualization, i.e. its INFINITESIMAL_MOTIONS. In your polymake file the INFINITESIMAL_MOTIONS are stored as follows:

> polymake my_framework.poly INFINITESIMAL_MOTIONS INFINITESIMAL_MOTIONS 1/2 1/3 -1/2 1 0 0 0 0 1/2 1/3 1 0 1/2 1 0 0 1 0 1 0 1 0 1 0 -1 1/3 -1/2 0 -1/2 0 0 1

Since the framework has four nodes in dimension two the matrix of INFINITESIMAL_MOTIONS has eight columns. The first two columns contain the motion of the first node, column three and four the coordinates of the motion of the second node, and so on. Each row of the matrix corresponds to one INFINITESIMAL_MOTIONS of the framework. The linear span of the rows yields all infinitesimal motions of the framework.

visualization of infinitesimal motions

To add these motions to the visualization use the following command:

> polymake my_framework.poly "VISUAL->INFINITESIMAL_MOTIONS(0)"

The zero in brackets makes polymake show each motion in separate window. If it is omitted then all motions are displayed in one window. Using the JavaView control panel you may still select all motions separately since every motion is its own geometry. Comparing the text output with the visualization we easily see, that the first motion moves only the nodes zero and one, whereas the third motion is a translation of the whole framework by the vector 1 0. In addition to the motions you may also visualize the INFINITESIMAL_PATTERNS and the INFINITESIMAL_RIGID_COMPONENTS by adding one or both of them to the comamnd line as follows as above. The INFINITESIMAL_RIGID_COMPONENTS is a partition of the nodes of the framework into rigid parts:

> polymake my_framework.poly INFINITESIMAL_RIGID_COMPONENTS INFINITESIMAL_RIGID_COMPONENTS {{0 1} {0 3} {1 2} {2 3}} {{0 1} {0 3} {1 2} {2 3}} {{0 1 2 3}} {{0 1} {0 3} {1 2} {2 3}}

This reproves that the third motion is a translation, since the entire framework stays rigid.

Expansive Motions

The expansive motions are motions of the framework where the distance between the nodes either expand or stay constant. These are of particular interest since they allow to avoid collisions and have helped to solve the Carpenter's Problem. Consider the following framework:

A Laman graph with one edge removed
> polymake laman_minus_one.poly FRAMEWORK FRAMEWORK (<2 8> {1 2 7 8}) (<5 12> {0 2}) (<11 12> {0 1 3}) (<11 6> {2 4 7}) (<7 2> {3 5 6}) (<5 4> {4 6 7}) (<8 5> {4 5 7}) (<8 8> {0 3 5 6 8}) (<4 4> {0 7})

The coordinates of the nodes are given in between the angle brackets < ... > followed by an adjacency list, i.e. the first node 0 has coordinates 2 8 and neighbors 1 2 7 8. This framework has only one degree of freedom and allows one single expansive motion:

> polymake laman_minus_one.poly N_DEGREES_OF_FREEDOM EXPANSIVE_MOTIONS N_DEGREES_OF_FREEDOM 1 EXPANSIVE_MOTIONS 0 0 -4/9 1/3 -4/9 1 2/3 1 2 -1/3 4/3 -1 1 0 0 0 0 0

A Laman graph with one edge removed and its expansive
motions, patterns, and rigid components

To get the picture on the right use the following command:

> polymake laman_minus_one.poly "VISUAL->EXPANSIVE"

It will display all EXPANSIVE_MOTIONS, EXPANSIVE_PATTERNS and EXPANSIVE_RIGID_COMPONENTS in one window and is shorthand for "VISUAL->EXPANSIVE_MOTIONS->EXPANSIVE_PATTERNS->EXPANSIVE_RIGID_COMPONENTS" . If javaview is used for visualization you may use the display dialog to show only some of the information. Another option is to set the optional parameter one_window of EXPANSIVE to 0 using the command "VISUAL->EXPANSIVE(0)" , such that every motion is displayed in its own window. The picature on the right shows the framework with thick black edges. The red arrows represent the motion of the nodes. The thin edges appear in two colors: green indicating that the distance between the adjacent nodes increases; gray indicating that the edge length stays constant. The red regions are the rigid components of the motion.