cp's OEIS Frontend

A graph is called rigid if, when we fix the length of each edge, it has only finitely many embeddings in the plane. A graph is called minimally rigid (or a Laman graph) if there is no edge that can be omitted while keeping the rigidity property. Laman graphs can be constructed by applying successively Henneberg moves (of type I or type II), starting with the graph that consists of two vertices joined by an edge. Here we consider Laman graphs that can be obtained by using only Henneberg type I moves, which means: adding one vertex and joining it with two different existing vertices.

All the Laman graphs (in other words, minimally rigid graphs) can be constructed by the inductive Henneberg construction, i.e., a sequence of Henneberg steps starting from K_2. A new vertex added by a Henneberg move is connected with two or three of the previously existing vertices. Hence, the chromatic number of a Laman graph can be 2, 3 or 4. One can hypothesize that the set of 3-chromatic Laman graphs is the largest and that bipartite graphs are relatively rare. The first nontrivial bipartite Laman graph is K_{3,3}. An infinite sequence of such graphs can be obtained from K_{3,3} by Henneberg moves of the first type (i.e., adding a vertex and connecting it with two of the existing vertices from the one part).

The Laman number gives the number of (complex) embeddings of a minimally rigid graph in 2D, modulo translations and rotations, when the edge lengths of the graph are chosen generically. In general, this number is larger than the number of real embeddings. Equivalently, the Laman number of a graph is the number of complex solutions of the quadratic polynomial system {x_1 = y_1 = x_2 = 0, y_2 = l(1,2), (x_i - x_j)^2 + (y_i - y_j)^2 = l(i,j)^2}, for all (i,j) such that the vertices i and j are connected by an edge (w.l.o.g. we assume that there is an edge between the vertices 1 and 2). The quantities l(i,j) correspond to the prescribed edge "lengths" (they can also be complex numbers).

A graph that is constructed only by Henneberg moves of type 1 (i.e., adding one new vertex and connecting it with two existing vertices), has Laman number 2^(n-2). The smallest minimally rigid graph that cannot be constructed in this way, is the 3-prism graph with 6 vertices. Therefore the sequence grows faster than 2^(n-2) for n >= 6.

We know that a graph with n <= 13 vertices achieving the maximal Laman number is unique. We do not know if this is necessarily true for more vertices.

All the Laman graphs (in other words, minimally rigid graphs) can be constructed by the inductive Henneberg construction, i.e., a sequence of Henneberg steps starting from K_2. A new vertex added by a Henneberg move is connected with two or three of the previously existing vertices. Hence, the chromatic number of a Laman graph can be 2, 3 or 4. One can hypothesize that the set of 3-chromatic Laman graphs is the largest and that bipartite graphs are relatively rare. The simplest example of a 4-chromatic Laman graph is the Moser spindle.

All minimally rigid graphs in 3D on n vertices can be constructed from the minimally rigid graphs in 3D on n-1 vertices by use of three types of constructions called the Henneberg constructions. In the first type a new vertex is added to the graph and three new edges are added connecting the new vertex to three different vertices which were already part of the graph. In the second type of construction, two adjacent vertices, say v_1 and v_2, are selected. The edge between v_1 and v_2 is deleted. A new vertex w is added to the graph, as well as the edges (v_1,w), (v_2,w), (v_3,w), and (v_4,w), where v_3 and v_4 are other vertices of the graph. The third construction chooses two pairs of adjacent vertices v_1,v_2 and v_3,v_4, where v_3 might be equal to v_2. The edges (v_1,v_2) and (v_3,v_4) are deleted. A new vertex w is added to the graph. If v_2!=v_3, the edges (v_1,w), (v_2,w), (v_3,w), (v_4,w), and (v_5,w) are added, where v_5 is another vertex of the graph. If v_2=v_3, other two vertices v_5,v_6 are chosen and the edges (v_1,w), (v_2,w),(v_4,w), (v_5,w), and (v_6,w) are added.

The first two constructions preserve rigidity whereas the third does not necessarily preserve rigidity. Nevertheless the third construction is needed to get all minimally rigid graphs in 3D. Up to 11 vertices the first two constructions suffice.

Each of these three constructions adds one to the number of vertices and three to the number of edges, i.e., all those graphs have 3n-6 edges for n vertices. Not all graphs with that number of edges are minimally rigid in 3D.

Every minimally rigid graph in 3D is (3,6)-tight (A374745). - Georg Grasegger, Oct 17 2024

A 2n-vertex graph is (3/2,2)-sparse if every subgraph with k vertices has at most (3/2)k-2 edges, and (3/2,2)-tight if in addition it has exactly 3n-2 edges; see Lee and Streinu (2008). These graphs represent two-dimensional mechanical systems formed by 2n rigid bodies (links), connected at joints where exactly two links are pinned together and can rotate relative to each other, with the entire system having one degree of freedom and having no rigid subsystems. The vertices of the graph represent links and the edges represent joints.