A306420 Maximal Laman number among all minimally rigid graphs on n vertices.

1, 1, 2, 4, 8, 24, 56, 136, 344, 880, 2288, 6180, 15536, 42780

Offset: 1

Author

Christoph Koutschan, Feb 14 2019

Keywords

• nonn
• more

Comments

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.

Examples

			A graph with one vertex can be drawn in the plane in a unique way, and similarly the graph with two vertices connected by an edge. The unique minimally rigid graph with three vertices is the triangle, which admits two different embeddings (they differ by reflection). The unique minimally rigid graph with four vertices is a quadrilateral with one diagonal (i.e., we have five edges). By fixing the diagonal, each of the two triangles can be flipped independently, yielding four different embeddings.
		

References

• J. Capco, M. Gallet, G. Grasegger, C. Koutschan, N. Lubbes, J. Schicho, The number of realizations of a Laman graph, SIAM Journal on Applied Algebra and Geometry 2(1), pp. 94-125, 2018.
• I. Z. Emiris, E. P. Tsigaridas, A. E. Varvitsiotis, Algebraic methods for counting Euclidean embeddings of graphs. Graph Drawing: 17th International Symposium, pp. 195-200, 2009.
• G. Grasegger, C. Koutschan, E. Tsigaridas, Lower bounds on the number of realizations of rigid graphs, Experimental Mathematics, 2018 (doi: 10.1080/10586458.2018.1437851).

Links

• Jose Capco, Nauty plugin to compute maximal Laman numbers.
• Jose Capco, Matteo Gallet, Georg Grasegger, Christoph Koutschan, Niels Lubbes, and Josef Schicho, The number of realizations of a Laman graph (website).
• Jose Capco, Matteo Gallet, Georg Grasegger, Christoph Koutschan, Niels Lubbes, and Josef Schicho, The number of realizations of a Laman graph, arXiv:1701.05500 [math.AG], 2017
• Ioannis Z. Emiris and Guillaume Moroz, The assembly modes of rigid 11-bar linkages, IFToMM 2011 World Congress, Guanajuato, Mexico, 2011; arXiv:1010.6214 [cs.RO], 2010-2017.
• Georg Grasegger, Explorations on the number of realizations of minimally rigid graphs, arXiv:2502.04736 [math.CO], 2025. See p. 24.
• Georg Grasegger, Christoph Koutschan, and Elias Tsigaridas, Lower bounds on the number of realizations of rigid graphs, arXiv:1710.08237 [math.CO], 2017-2018.
• Christoph Koutschan and Jose Capco, Latest C++ implementation [Broken link]
• G. Laman, On Graphs and Rigidity of Planar Skeletal Structures, J. Engineering Mathematics, Vol. 4, No. 4, 1970, pp. 331-340.
• H. Pollaczek-Geiringer, Über die Gliederung ebener Fachwerke, Zeitschrift für Angewandte Mathematik und Mechanik, Vol. 7, No. 1, 1927, pp. 58-72.
• Wikipedia, Laman graph

Crossrefs

Cf. A227117, A273468.

Programs

nauty

# See nauty plugin in Links.

Extensions

a(13) computed by Jose Capco added by Christoph Koutschan, Feb 15 2019

a(14) computed and added by Jose Capco, Oct 02 2023