|
%I #38 Oct 02 2023 13:48:39
%S 1,1,2,4,8,24,56,136,344,880,2288,6180,15536,42780
%N Maximal Laman number among all minimally rigid graphs on n vertices.
%C 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 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 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 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 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 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 Jose Capco, <a href="https://github.com/jcapco/lnumber">Nauty plugin</a> to compute maximal Laman numbers.
%H Jose Capco, M. Gallet, G. Grasegger, C. Koutschan, N. Lubbes and J. Schicho, <a href="http://www.koutschan.de/data/laman/">The number of realizations of a Laman graph (website)</a>.
%H Jose Capco, M. Gallet, G. Grasegger, C. Koutschan, N. Lubbes, J. 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 I. Z. Emiris and G. 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 G. Grasegger, C. Koutschan, and E. 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 C. Koutschan and J. Capco, <a href="http://svn.risc.uni-linz.ac.at/websvn/dl.php?repname=jcapco&path=%2Flnumber%2F&rev=0&isdir=1">Latest C++ implementation</a>
%H G. Laman, <a href="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 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 Wikipedia, <a href="https://en.wikipedia.org/wiki/Laman_graph">Laman graph</a>
%e 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 See Nauty plugin in Links.
%Y Cf. A227117, A273468.
%K nonn,more
%O 1,3
%A _Christoph Koutschan_, Feb 14 2019
%E a(13) computed by _Jose Capco_ added by _Christoph Koutschan_, Feb 15 2019
%E a(14) computed and added by _Jose Capco_, Oct 02 2023
|
