Laman graph

Laman graphs are named after Gerard Laman, of the University of Amsterdam, who in 1970 used them to characterize rigid planar structures.

[1] However, this characterization, the Geiringer–Laman theorem, had already been discovered in 1927 by Hilda Geiringer.

[2] Laman graphs arise in rigidity theory: if one places the vertices of a Laman graph in the Euclidean plane, in general position, there will in general be no simultaneous continuous motion of all the points, other than Euclidean congruences, that preserves the lengths of all the graph edges.

A graph is rigid in this sense if and only if it has a Laman subgraph that spans all of its vertices.

If n points in the plane are given, then there are 2n degrees of freedom in their placement (each point has two independent coordinates), but a rigid graph has only three degrees of freedom (the position of a single one of its vertices and the rotation of the remaining graph around that vertex).

Intuitively, adding an edge of fixed length to a graph reduces its number of degrees of freedom by one, so the 2n − 3 edges in a Laman graph reduce the 2n degrees of freedom of the initial point placement to the three degrees of freedom of a rigid graph.

A pointed pseudotriangulation is a planar straight-line drawing of a graph, with the properties that the outer face is convex, that every bounded face is a pseudotriangle, a polygon with only three convex vertices, and that the edges incident to every vertex span an angle of less than 180 degrees.

The same notation can be used to describe other important families of sparse graphs, including trees, pseudoforests, and graphs of bounded arboricity.

[4][5] Based on this characterization, it is possible to recognize n-vertex Laman graphs in time O(n2), by simulating a "pebble game" that begins with a graph with n vertices and no edges, with two pebbles placed on each vertex, and performs a sequence of the following two kinds of steps to create all of the edges of the graph: If these operations can be used to construct an orientation of the given graph, then it is necessarily (2,3)-sparse, and vice versa.

[7] Before Laman's and Geiringer's work, Lebrecht Henneberg characterized the two-dimensional minimally rigid graphs (that is, the Laman graphs) in a different way.

For instance, the complete bipartite graph K3,3 may be formed using the first operation to form a triangle and then applying the second operation to subdivide each edge of the triangle and connect each subdivision point with the opposite triangle vertex.