Laman graph

In graph theory, the Laman graphs are a family of sparse graphs describing the minimally rigid systems of rods and joints in the plane. Formally, a Laman graph is a graph on n vertices such that, for all k, every k-vertex subgraph has at most 2k − 3 edges, and such that the whole graph has exactly 2n − 3 edges. Laman graphs are named after Gerard Laman, of the University of Amsterdam, who in 1970 used them to characterize rigid planar structures. This characterization, however, had already been discovered in 1927 by Hilda Geiringer.

The Moser spindle, a planar Laman graph drawn as a pointed pseudotriangulation

The complete bipartite graph K_3,3, a non-planar Laman graph

Rigidity

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. Thus, the Laman graphs are exactly the minimally rigid graphs, and they form the bases of the two-dimensional rigidity matroids.

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. However, not every graph with 2n − 3 edges is rigid; the condition in the definition of a Laman graph that no subgraph can have too many edges ensures that each edge contributes to reducing the overall number of degrees of freedom, and is not wasted within a subgraph that is already itself rigid due to its other edges.

Planarity

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 graphs that can be drawn as pointed pseudotriangulations are exactly the planar Laman graphs. However, Laman graphs have planar embeddings that are not pseudotriangulations, and there are Laman graphs that are not planar, such as the utility graph K_3,3.

Sparsity

Lee & Streinu (2008) and Streinu & Theran (2009) define a graph as being $(k,\ell )$-sparse if every nonempty subgraph with $n$ vertices has at most $kn-\ell$ edges, and $(k,\ell )$-tight if it is $(k,\ell )$-sparse and has exactly $kn-\ell$ edges. Thus, in their notation, the Laman graphs are exactly the (2,3)-tight graphs, and the subgraphs of the Laman graphs are exactly the (2,3)-sparse graphs. The same notation can be used to describe other important families of sparse graphs, including trees, pseudoforests, and graphs of bounded arboricity.

Based on this characterization, it is possible to recognize n-vertex Laman graphs in time O(n²), 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:

• Create a new directed edge connecting any two vertices that both have two pebbles, and remove one pebble from the start vertex of the new edge.
• If an edge points from a vertex u with at most one pebble to another vertex v with at least one pebble, move a pebble from v to u and reverse the edge.

If these operations can be used to construct an orientation of the given graph, then it is necessarily (2,3)-sparse, and vice versa. However, faster algorithms are possible, running in time $O(n^{3/2}{\sqrt {\log n}})$, based on testing whether doubling one edge of the given graph results in a multigraph that is (2,2)-tight (equivalently, whether it can be decomposed into two edge-disjoint spanning trees) and then using this decomposition to check whether the given graph is a Laman graph. Network flow techniques can be used to test whether a planar graph is a Laman graph more quickly, in time $O(n\log ^{3}n)$.

Henneberg construction

Henneberg construction of the Moser spindle

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. Henneberg showed that the minimally rigid graphs on two or more vertices are exactly the graphs that can be obtained, starting from a single edge, by a sequence of operations of the following two types:

1. Add a new vertex to the graph, together with edges connecting it to two previously existing vertices.
2. Subdivide an edge of the graph, and add an edge connecting the newly formed vertex to a third previously existing vertex.

A sequence of these operations that forms a given graph is known as a Henneberg construction of the graph. For instance, the complete bipartite graph K_3,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.

See also

• Geiringer-Laman theorem