login
A306420
Maximal Laman number among all minimally rigid graphs on n vertices.
1
1, 1, 2, 4, 8, 24, 56, 136, 344, 880, 2288, 6180, 15536, 42780
OFFSET
1,3
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.
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, M. Gallet, G. Grasegger, C. Koutschan, N. Lubbes and J. Schicho, The number of realizations of a Laman graph (website).
Jose Capco, M. Gallet, G. Grasegger, C. Koutschan, N. Lubbes, J. Schicho, The number of realizations of a Laman graph, arXiv:1701.05500 [math.AG], 2017
I. Z. Emiris and G. Moroz, The assembly modes of rigid 11-bar linkages, IFToMM 2011 World Congress, Guanajuato, Mexico, 2011; arXiv:1010.6214 [cs.RO], 2010-2017.
G. Grasegger, C. Koutschan, and E. Tsigaridas, Lower bounds on the number of realizations of rigid graphs, arXiv:1710.08237 [math.CO], 2017-2018.
C. Koutschan and J. Capco, Latest C++ implementation
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
EXAMPLE
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.
PROG
(nauty) # See nauty plugin in Links.
CROSSREFS
Sequence in context: A078222 A078223 A291405 * A361726 A333971 A231721
KEYWORD
nonn,more
AUTHOR
Christoph Koutschan, Feb 14 2019
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
STATUS
approved