cp's OEIS Frontend

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

%I A306420 #48 Feb 17 2025 12:20:35
%S A306420 1,1,2,4,8,24,56,136,344,880,2288,6180,15536,42780
%N A306420 Maximal Laman number among all minimally rigid graphs on n vertices.
%C A306420 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).
%C A306420 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.
%C A306420 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.
%D A306420 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.
%D A306420 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.
%D A306420 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).
%H A306420 Jose Capco, <a href="https://github.com/jcapco/lnumber">Nauty plugin</a> to compute maximal Laman numbers.
%H A306420 Jose Capco, Matteo Gallet, Georg Grasegger, Christoph Koutschan, Niels Lubbes, and Josef Schicho, <a href="http://www.koutschan.de/data/laman/">The number of realizations of a Laman graph (website)</a>.
%H A306420 Jose Capco, Matteo Gallet, Georg Grasegger, Christoph Koutschan, Niels Lubbes, and Josef Schicho, <a href="https://arxiv.org/abs/1701.05500">The number of realizations of a Laman graph</a>, arXiv:1701.05500 [math.AG], 2017
%H A306420 Ioannis Z. Emiris and Guillaume Moroz, <a href="https://arxiv.org/abs/1010.6214">The assembly modes of rigid 11-bar linkages</a>, IFToMM 2011 World Congress, Guanajuato, Mexico, 2011; arXiv:1010.6214 [cs.RO], 2010-2017.
%H A306420 Georg Grasegger, <a href="https://arxiv.org/abs/2502.04736">Explorations on the number of realizations of minimally rigid graphs</a>, arXiv:2502.04736 [math.CO], 2025. See p. 24.
%H A306420 Georg Grasegger, Christoph Koutschan, and Elias Tsigaridas, <a href="https://arxiv.org/abs/1710.08237">Lower bounds on the number of realizations of rigid graphs</a>, arXiv:1710.08237 [math.CO], 2017-2018.
%H A306420 Christoph Koutschan and Jose Capco, <a href="http://svn.risc.uni-linz.ac.at/websvn/dl.php?repname=jcapco&amp;path=%2Flnumber%2F&amp;rev=0&amp;isdir=1">Latest C++ implementation</a> [Broken link]
%H A306420 G. Laman, <a href="https://web.archive.org/web/20210507003843/http://www.wisdom.weizmann.ac.il/~vision/courses/2010_2/papers/OnGraphsAndRigidity.pdf">On Graphs and Rigidity of Planar Skeletal Structures</a>, J. Engineering Mathematics, Vol. 4, No. 4, 1970, pp. 331-340.
%H A306420 H. Pollaczek-Geiringer, <a href="https://doi.org/10.1002/zamm.19270070107">Über die Gliederung ebener Fachwerke</a>, Zeitschrift für Angewandte Mathematik und Mechanik, Vol. 7, No. 1, 1927, pp. 58-72.
%H A306420 Wikipedia, <a href="https://en.wikipedia.org/wiki/Laman_graph">Laman graph</a>
%e A306420 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.
%o A306420 (nauty) # See nauty plugin in Links.
%Y A306420 Cf. A227117, A273468.
%K A306420 nonn,more
%O A306420 1,3
%A A306420 _Christoph Koutschan_, Feb 14 2019
%E A306420 a(13) computed by _Jose Capco_ added by _Christoph Koutschan_, Feb 15 2019
%E A306420 a(14) computed and added by _Jose Capco_, Oct 02 2023