Laman Graph - Henneberg Construction

Henneberg Construction

Long before Laman'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.