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.[1]
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 motion of all the points, other than Euclidean congruences, that preserves the lengths of all the graph edges, and the Laman graphs are the minimal graphs with this property. Intuitively, each edge reduces the number of degrees of freedom in the system of points 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 that are sufficient to describe any Euclidean congruence. The condition that no subgraph 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.
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.[2] However, there are Laman graphs that are not planar, such as the utility graph K3,3.