Laman graph

From Wikipedia, the free encyclopedia
Jump to: navigation, search
The Moser spindle, a planar Laman graph drawn as a pointed pseudotriangulation
The complete bipartite graph K3,3, a non-planar 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.[1]

Rigidity[edit]

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. 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[edit]

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, Laman graphs have planar embeddings that are not pseudotriangulations, and there are Laman graphs that are not planar, such as the utility graph K3,3.

Sparsity[edit]

Streinu & Theran (2008) define a graph as being (k,l)-sparse if every nonempty subgraph with n vertices has at most kn-l edges, and (k,l)-tight if it is (k,l)-sparse and has exactly kn-l 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.[3]

Henneberg construction[edit]

Henneberg construction of the Moser spindle

Long before Laman's work, Lebrecht Henneberg characterized the two-dimensional minimally rigid graphs (that is, the Laman graphs) in a different way.[4] 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 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.

References[edit]

  1. ^ Laman, G. (1970), "On graphs and the rigidity of plane skeletal structures", J. Engineering Mathematics 4 (4): 331–340, doi:10.1007/BF01534980, MR 0269535 .
  2. ^ Haas, Ruth; Orden, David; Rote, Günter; Santos, Francisco; Servatius, Brigitte; Servatius, Herman; Souvaine, Diane; Streinu, Ileana; Whiteley, Walter (2005), "Planar minimally rigid graphs and pseudo-triangulations", Computational Geometry Theory and Applications 31 (1–2): 31–61, doi:10.1016/j.comgeo.2004.07.003, MR 2131802 .
  3. ^ Streinu, I.; Theran, L. (2009), "Sparse hypergraphs and pebble game algorithms", European Journal of Combinatorics 30 (8): 1944–1964, arXiv:math/0703921, doi:10.1016/j.ejc.2008.12.018 .
  4. ^ Henneberg, L. (1911), Die graphische Statik der starren Systeme, Leipzig