|
|
A306420
|
|
Maximal Laman number among all minimally rigid graphs on n vertices.
|
|
0
|
|
|
1, 1, 2, 4, 8, 24, 56, 136, 344, 880, 2288, 6180, 15536, 42780
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
See Nauty plugin in Links.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
a(14) computed and added by Jose Capco, Oct 02 2023
|
|
STATUS
|
approved
|
|
|
|