Laman graph
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.
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. However, there are Laman graphs that are not planar, such as the utility graph K3,3.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, 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
Gerard Laman
Gerard Laman , was a Dutch mathematician who worked on graph theory.He completed high school studies at the Stedelijk Gymnasium Leiden in 1942...
, of the University of Amsterdam, who in 1970 used them to characterize rigid planar structures.
Laman graphs arise in rigidity theory: if one places the vertices of a Laman graph in the Euclidean plane, in general position
General position
In algebraic geometry, general position is a notion of genericity for a set of points, or other geometric objects. It means the general case situation, as opposed to some more special or coincidental cases that are possible...
, there will in general be no simultaneous motion of all the points, other than Euclidean congruences
Congruence (geometry)
In geometry, two figures are congruent if they have the same shape and size. This means that either object can be repositioned so as to coincide precisely with the other object...
, 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
Degrees of freedom (engineering)
In mechanics, degrees of freedom are the set of independent displacements and/or rotations that specify completely the displaced or deformed position and orientation of the body or system...
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
Pseudotriangle
In Euclidean plane geometry, a pseudotriangle is the simply connected subset of the plane that lies between any three mutually tangent convex sets...
is a planar straight-line drawing
Planar straight-line graph
Planar straight-line graph is a term used in computational geometry for an embedding of a planar graph in the plane such that its edges are mapped into straight line segments...
of a graph, with the properties that the outer face is convex, that every bounded face is a pseudotriangle
Pseudotriangle
In Euclidean plane geometry, a pseudotriangle is the simply connected subset of the plane that lies between any three mutually tangent convex sets...
, 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
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
Laman graphs. However, there are Laman graphs that are not planar, such as the utility graph K3,3.