Laman graph

From Wikipedia, the free encyclopedia

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.

Every pointed pseudotriangulation is a Laman graph, and every planar Laman graph can be realized as a pointed pseudotriangulation.^[2] However, there are Laman graphs that are not planar, such as the complete bipartite graph K_3,3.

[edit] References