The LEGO company is developing a piece of software called Digital Designer. In this program you can build virtual LEGO models on the computer. Most modern LEGO models contain hinges that allow different parts of the model to move relative to one another. The aim is to be able to simulate these movements in Digital Designer as well.

To simulate the movements of a LEGO structure one first makes an abstract model of the structure that neglects all details except how the moving parts are interconnected. This gives a graph which is a kind of "skeleton" of the LEGO structure. The graph to the left is such a skeleton of the dinosaur above (except for its arms). When the graph is acyclic like this one, all movements are independent. The movement of the teeth of the dinosaur (corresponding to leftmost nodes) is independent of the movement of its tail (corresponding to the rightmost nodes) -- so the dinosaur will not start biting just because you pull its tail (note! Don't be too sure that the same will hold for a real dinosaur).

LEGO structures in which all movements are independent are quite simple to simulate. It only gets non-trivial when the movements are interdependent, that is, when the graph is cyclic. The animation to the left shows a LEGO structure which in planar kinematics is called a four-bar linkage. It corresponds to the simple cyclic graph with four nodes and four edges (a quadrangle). All movements in this structure are interdependent.

To the left is a picture of a LEGO Technics excavator and the corresponding graph. The graph has several cycles, that is, several interdependent hinges. This makes it complicated to simulate its movement.

Next	(thanks to LEGO for providing the bricks and to my nephew for building the excavator)