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:
- Add a new vertex to the graph, together with edges connecting it to two previously existing vertices.
- 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.
Read more about this topic: Laman Graph
Famous quotes containing the word construction:
“There is, I think, no point in the philosophy of progressive education which is sounder than its emphasis upon the importance of the participation of the learner in the formation of the purposes which direct his activities in the learning process, just as there is no defect in traditional education greater than its failure to secure the active cooperation of the pupil in construction of the purposes involved in his studying.”
—John Dewey (1859–1952)