Lower Bounds on the Number of Realizations of Rigid Graphs

Figures & data

Figure 1. Henneberg steps of different types in dimension 2; A dashed line indicates that this edge can exist but does not need to.

Figure 2. Vertex splitting.

Table 1. Henneberg constructions and increase of Laman numbers.

Type	G	Lam2(G)	G′	Lam2(G′)	Factor
2c	1269995	56	31004235	96	1.71
2c	7916	24	481867	44	1.83
2b	186013	32	170989214	136	4.25
2c	183548	32	170989214	136	4.25
2c	20042142	64	11177989553	344	5.37
2c	4593214614	128	22301628505804	808	6.31
2c	1248809223262	256	2960334732174949	1976	7.72
2c	1710909647295913	512	15006592507478215906	4816	9.41

Figure 3. Caterpillar construction with four copies of the three-prism graph.

Figure 4. Fan construction with four copies of the three-prism graph.

Figure 5. Bases for the generalized fan construction and their encodings.

Figure 6. Unique Laman graphs with 6 ⩽ n ⩽ 12 with maximal number of embeddings (see Table 2, encodings see Table 8).

Table 2. Minimal and maximal Laman number among all n-vertex Laman graphs; the minimum is 2^{n − 2} and it is achieved, for example, on Laman graphs that are constructible by using only Henneberg steps of type 1. The row labeled with “lower” contains the bounds from [Emiris et al. 09].

n	6	7	8	9	10	11	12
min	16	32	64	128	256	512	1024
M2(n)	24	56	136	344	880	2288	6180
lower	24	48	96	288	576	—	—

Table 3. With M_T(n) we denote the maximal Laman number of the graphs in T(n). In the row below we give the highest Laman numbers that we have found so far by looking at graphs in S(n) (exhaustive for n ⩽ 15 but incomplete for n > 15).

n	12	13	14	15	16	17	18
MT(n)	5952	15,056	39,696	105,384	277,864	731,336	1,953,816
MS(n)	6180	15,536	42,780	112,752	312,636	870,414	2,237,312

Table 4. Growth rates (rounded) of the lower bounds. For n ⩽ 12 these values are proven to be the best achievable ones; for n > 12 the values are just the best we found by experiments, hence it is possible that there are better ones. The drawings of the graphs corresponding to the last three columns are given in Figure 5. The encodings for the graphs can be found at: caterpillar (Table 8), fan T(n) (Table 9), fan (Table 11), 31-fan (Table 12), 254-fan (Table 13), 223-fan and 239-fan (Table 14), 7916-fan (Table 15).

n	caterpillar	fan T(n)	fan	31-fan	254-fan	7916-fan
6	2.21336	2.28943		2	2	—
7	2.23685	2.30033		2.28943	2	2
8	2.26772	2.32542		2.30033	2.28943	2
9	2.30338	2.35824		2.35216	2.30033	2.28943
10	2.33378	2.38581		2.35824	2.35216	2.30033
11	2.36196	2.41159		2.38581	2.35824	2.35216
12	2.39386	2.43198		2.43006	2.39802	2.35824
13	2.40453	2.44156	2.44498	2.44772	2.42197	2.39802
14	2.43185	2.45868	2.46087	2.46391	2.44251	2.42197
15	2.44695	2.47445		2.47076	2.45031	2.42906
16	2.46890	2.48657		2.48794	2.47166	2.43712
17	2.48875	2.49668	2.49779	2.49160	2.48043	2.46341
18	2.49378	2.50798

Figure 7. Laman graphs in T(n) with 12 ⩽ n ⩽ 18 vertices; for each n the graph with the largest Laman number among the Laman graphs in T(n) is displayed. The corresponding Laman numbers are given in Table 3 (encodings see Table 9).

Figure 8. Circular embedding of the Laman graphs with maximal Laman numbers for 6 ⩽ n ⩽ 12. Note that these are the same graphs that are displayed in Figure 6.

Figure 9. For n = 13, …, 18, we display the graph from S(n) with the highest Laman number (given in Table 3) found so far (encodings see Table 10).

Figure 10. Laman graphs with 7 ⩽ n ⩽ 12 vertices that have the four-vertex Laman graph (encoded as 31) as a subgraph; below their Laman numbers are given. In some cases, there are several Laman graphs with this subgraph property and with the same Laman number, but among all Laman graphs that have this subgraph there does not exist one with higher Laman number (encodings see Table 12).

Figure 11. Growth rates of the lower bounds (red = caterpillar construction, blue = fan construction, green = 31-fan construction, fuchsia = 254-fan construction, brown = 7916-fan construction). The light colors indicate values that were not found by exhaustive search and which therefore could possibly be improved.

Figure 12. Henneberg steps of different types in dimension 3; a dashed line indicates that this edge can exist but does not need to.

Figure 13. Flexible graph constructed by a Henneberg move of type 3.

Table 5. Henneberg constructions and increase of 3D-Laman numbers.

Type	G	Lam3(G)	G′	Lam3(G′)	Factor
3v	11717490611	512	9634462543324	128	0.25
3v	49724126	160	18848282483	64	0.40
3v	515806	48	203906043	32	0.66
2	981215	24	31965132	24	1.00
3x	16350	16	1973983	16	1.00
2, 3x	1973983	16	49524604	128	8.00
3x	384510	16	49724126	160	10.00
3v	382463	16	49724126	160	10.00
3x	15661790	32	7309884067	512	16.00
3x	2000476603	48	2704137746603	1088	22.66

Figure 14. Geiringer graphs with 6 ⩽ n ⩽ 10 vertices; for each n the (unique) graph with maximal number of embeddings is depicted. The corresponding 3D-Laman numbers M₃(n) are given in Table 6 (encodings see Table 16).

Figure 15. Growth rates of the lower bounds (red = caterpillar construction, blue = fan construction, green = generalized fan construction).

Table 6. Minimal and maximal 3D-Laman number among all n-vertex Geiringer graphs; the row labeled with “min” contains the lowest 3D-Laman number which is found by computation. The row labeled with “upper” contains the bounds from [Borcea and Streinu 04].

n	6	7	8	9	10	11	12
min	8	16	24	48	76
M3(n)	16	48	160	640	2560
upper	40	224	1344	8448	54,912	366,080	2,489,344

Table 7. Growth rates (rounded) of the lower bounds. The encodings for the graphs can be found at: caterpillar (Table 16), fan (Table 17), generalized fan (Table 18).

n	caterpillar	fan	generalized fan
6	2.51984	2	—
7	2.63215	2.51984	2
8	2.75946	2.63215	2.51984
9	2.93560	2.95155	2.82843
10	3.06825	3.06681	2.95155

Table 8. Graph encodings for the graphs with maximal Laman number (see Figure 6).

n	Graph encoding	Laman number
6	7916	24
7	1269995	56
8	170989214	136
9	11177989553	344
10	4778440734593	880
11	18120782205838348	2288
12	252590061719913632	6180

Table 9. Graph encodings for the graphs in T(n) (see Figure 7).

n	Graph encoding	Laman number
12	757486969329934592	5952
13	3102079810848683155456	15,056
14	12393113433401056197689344	39,696
15	101535867160732294622504828928	105,384
16	283980994531838217547205604229120	277,864
17	65135173642079980743135145171586662400	731,336
18	9061092056503516236392931137633162134437921	1,953,816

Table 10. Graph encodings for the graphs in S(n) from Figure 9.

n	Graph encoding	Laman number
13	2731597771584836257824	15,536
14	3932631430916370534240769	42,780
15	94091005932357252120217796609	112,752
16	892527555716690691964688718172672	312,636
17	97035633928660816927022803757023440896	870,414
18	1132478330239973528711451061872988363235584	2,237,312

Table 11. Graph encodings for graphs which contain the triangle as subgraph and have high Laman number.

n	Graph encoding	Laman number
13	517844367551685511200	15,268
14	8465213527269428904345612	40,088
17	34561064106536153162036856640676376576	1,953,816

Table 12. Graph encodings for the graphs from Figure 10 and further graphs which contain the 4-vertex Laman graph as subgraph and have high Laman number.

n	Graph encoding	Laman number
7	127575	48
8	7654183	112
9	11987422577	288
10	26665598300033	688
11	18226243755613920	1760
12	57080320167818985484	4864
13	1845359412452332949520	12,616
14	2116433716010931973523488	32,984
15	366442648507105101448244891666	83,792
16	1054776952932226148552313881544736	224,976
17	260539761471154896904085679883542331426	570,544

Table 13. Laman graphs which have the 5-vertex graph with encoding 254 as subgraph.

n	Graph encoding	Laman number
6	3326	16
7	190686	32
8	210799326	96
9	27047004894	224
10	220302198846	576
11	511412109882689	1376
12	270814819769185025	3648
13	2585030414085585133728	9472
14	6356539347198988132306956	24,752
15	1109200018557493535348018405392	62,416
16	5598668013338146547621855406197248	168,256
17	176789006904155934327358957938973624416	433,920

Table 14. Laman graphs which have the 5-vertex graph with encoding 223 and 239 as subgraph, respectively.

n	Graph encoding	Laman number	Graph encoding	Laman number
6	12511	16	10479	16
7	111335	32	103805	32
8	6419031	96	12339295	96
9	812960551	224	1024072271	224
10	209151514913	576	221350536519	576
11	110640260854593	1376	18441562579184833	1376
12	37616617704925531361	3648	21047011153048344071	3648

Table 15. Laman graphs which have the three-prism with encoding 7916 as subgraph.

n	Graph encoding	Laman number
7	120478	48
8	6475132	96
9	51946608057	288
10	18284890201676	672
11	5366995734673421	1728
12	523614257391638273	4128
13	2066305871268252766241	10,944
14	40197303758420411293510144	28,416
15	61903368089062917457613881376	70,656
16	11358585136343922383033065301099552	177,408
17	33233417861308024077754506274593047824	486,528

Table 16. Graph encodings for the Geiringer graphs with maximal 3D-Laman number (see Figure 14).

n	Graph encoding	3D-Laman number
4	63	2
5	511	4
6	16350	16
7	515806	48
8	49724126	160
9	7345971057	640
10	3559487592083	2560

Table 17. Graph encodings for the Geiringer graphs which contain the tetrahedron.

n	Graph encoding	3D-Laman number
5	511	4
6	7679	8
7	257911	32
8	16559991	96
9	4076665507	448
10	4894450217603	1664

Table 18. Graph encodings for the Geiringer graphs which contain the double tetrahedron.

n	Graph encoding	3D-Laman number
6	7679	8
7	237055	16
8	14937975	64
9	38164887119	256
10	3168405805643	896

[Emiris et al. 09] I. Z. Emiris, E. P. Tsigaridas, and A. E. Varvitsiotis. “Algebraic Methods for Counting Euclidean Embeddings of Graphs.” In Graph Drawing: 17th International Symposium, edited by D. Eppstein and E. R. Gamsners, pp. 195–200. New York: Springer, 2009.

 Google Scholar

[Borcea and Streinu 04] C. Borcea and I. Streinu. “The Number of Embeddings of Minimally Rigid Graphs.” Discrete. Comput. Geom. 31 (2004), 287–303.

 Web of Science ®Google Scholar