576:
17:
32:
160: − 3 edges is rigid; the condition in the definition of a Laman graph that no subgraph can have too many edges ensures that each edge contributes to reducing the overall number of degrees of freedom, and is not wasted within a subgraph that is already itself rigid due to its other edges.
587:
characterized the two-dimensional minimally rigid graphs (that is, the Laman graphs) in a different way. Henneberg showed that the minimally rigid graphs on two or more vertices are exactly the graphs that can be obtained, starting from a single edge, by a sequence of operations of the following two
147:
in their placement (each point has two independent coordinates), but a rigid graph has only three degrees of freedom (the position of a single one of its vertices and the rotation of the remaining graph around that vertex). Intuitively, adding an edge of fixed length to a graph reduces its number of
129:, that preserves the lengths of all the graph edges. A graph is rigid in this sense if and only if it has a Laman subgraph that spans all of its vertices. Thus, the Laman graphs are exactly the minimally rigid graphs, and they form the bases of the two-dimensional
383:
edges. Thus, in their notation, the Laman graphs are exactly the (2,3)-tight graphs, and the subgraphs of the Laman graphs are exactly the (2,3)-sparse graphs. The same notation can be used to describe other important families of
610:
may be formed using the first operation to form a triangle and then applying the second operation to subdivide each edge of the triangle and connect each subdivision point with the opposite triangle vertex.
180:, a polygon with only three convex vertices, and that the edges incident to every vertex span an angle of less than 180 degrees. The graphs that can be drawn as pointed pseudotriangulations are exactly the
508:
510:, based on testing whether doubling one edge of the given graph results in a multigraph that is (2,2)-tight (equivalently, whether it can be decomposed into two edge-disjoint
565:
352:
320:
239:
381:
288:
958:, Leibniz International Proceedings in Informatics (LIPIcs), vol. 144, Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 79:1–79:12,
422:
vertices and no edges, with two pebbles placed on each vertex, and performs a sequence of the following two kinds of steps to create all of the edges of the graph:
259:
184:
Laman graphs. However, Laman graphs have planar embeddings that are not pseudotriangulations, and there are Laman graphs that are not planar, such as the
1003:
426:
Create a new directed edge connecting any two vertices that both have two pebbles, and remove one pebble from the start vertex of the new edge.
156:
degrees of freedom of the initial point placement to the three degrees of freedom of a rigid graph. However, not every graph with 2
453:
of the given graph, then it is necessarily (2,3)-sparse, and vice versa. However, faster algorithms are possible, running in time
973:
934:
595:
Subdivide an edge of the graph, and add an edge connecting the newly formed vertex to a third previously existing vertex.
862:
1033:
745:
144:
456:
804:
114:
98:
450:
173:
1028:
592:
Add a new vertex to the graph, together with edges connecting it to two previously existing vertices.
97:, who in 1970 used them to characterize rigid planar structures. However, this characterization, the
525:
584:
36:
1023:
94:
325:
293:
212:
357:
264:
724:
126:
907:
Daescu, O.; Kurdia, A. (2009), "Towards an optimal algorithm for recognizing Laman graphs",
176:
of a graph, with the properties that the outer face is convex, that every bounded face is a
835:
776:
694:
660:
640:
515:
125:, there will in general be no simultaneous continuous motion of all the points, other than
575:
8:
389:
698:
644:
912:
889:
871:
839:
813:
780:
754:
728:
664:
514:) and then using this decomposition to check whether the given graph is a Laman graph.
244:
951:
997:
969:
930:
668:
784:
16:
959:
922:
893:
881:
823:
764:
702:
648:
130:
122:
831:
772:
768:
740:
682:
656:
118:
102:
843:
964:
857:
827:
799:
736:
732:
177:
169:
25:
885:
1017:
706:
511:
185:
21:
926:
628:
519:
393:
385:
181:
90:
62:
58:
50:
909:
Proc. 42nd Hawaii
International Conference on System Sciences (HICSS '09)
652:
397:
85: − 3 edges, and such that the whole graph has exactly 2
860:; Theran, L. (2009), "Sparse hypergraphs and pebble game algorithms",
599:
A sequence of these operations that forms a given graph is known as a
876:
818:
759:
720:
743:(2005), "Planar minimally rigid graphs and pseudo-triangulations",
631:(1970), "On graphs and the rigidity of plane skeletal structures",
917:
954:, in Bender, Michael A.; Svensson, Ola; Herman, Grzegorz (eds.),
31:
418:, by simulating a "pebble game" that begins with a graph with
403:
Based on this characterization, it is possible to recognize
603:
of the graph. For instance, the complete bipartite graph
89: − 3 edges. Laman graphs are named after
152: − 3 edges in a Laman graph reduce the 2
956:
27th Annual
European Symposium on Algorithms (ESA 2019)
950:
Rollin, Jonathan; Schlipf, Lena; Schulz, André (2019),
528:
459:
360:
328:
296:
267:
247:
215:
117:: if one places the vertices of a Laman graph in the
802:(2008), "Pebble game algorithms and sparse graphs",
949:
719:
681:
687:Zeitschrift fĂĽr Angewandte Mathematik und Mechanik
559:
502:
375:
346:
314:
282:
253:
233:
1015:
685:(1927), "Ăśber die Gliederung ebener Fachwerke",
449:If these operations can be used to construct an
140:points in the plane are given, then there are 2
746:Computational Geometry Theory and Applications
856:
437:with at least one pebble, move a pebble from
206:
65:of rods and joints in the plane. Formally, a
906:
579:Henneberg construction of the Moser spindle
1002:: CS1 maint: location missing publisher (
797:
503:{\displaystyle O(n^{3/2}{\sqrt {\log n}})}
433:with at most one pebble to another vertex
202:
990:Die graphische Statik der starren Systeme
987:
963:
916:
875:
817:
758:
570:
518:techniques can be used to test whether a
101:, had already been discovered in 1927 by
574:
241:-sparse if every nonempty subgraph with
30:
15:
522:is a Laman graph more quickly, in time
1016:
627:
583:Before Laman's and Geiringer's work,
148:degrees of freedom by one, so the 2
13:
24:, a planar Laman graph drawn as a
14:
1045:
952:"Recognizing planar Laman graphs"
863:European Journal of Combinatorics
429:If an edge points from a vertex
981:
943:
900:
850:
791:
723:; Orden, David; Rote, GĂĽnter;
713:
675:
621:
560:{\displaystyle O(n\log ^{3}n)}
554:
532:
497:
463:
341:
329:
309:
297:
228:
216:
81:-vertex subgraph has at most 2
1:
614:
407:-vertex Laman graphs in time
769:10.1016/j.comgeo.2004.07.003
174:planar straight-line drawing
163:
73:vertices such that, for all
7:
207:Streinu & Theran (2009)
197:
170:pointed pseudotriangulation
108:
26:pointed pseudotriangulation
10:
1050:
965:10.4230/LIPIcs.ESA.2019.79
828:10.1016/j.disc.2007.07.104
683:Pollaczek-Geiringer, Hilda
633:J. Engineering Mathematics
45:, a non-planar Laman graph
886:10.1016/j.ejc.2008.12.018
347:{\displaystyle (k,\ell )}
315:{\displaystyle (k,\ell )}
234:{\displaystyle (k,\ell )}
61:describing the minimally
707:10.1002/zamm.19270070107
396:, and graphs of bounded
376:{\displaystyle kn-\ell }
354:-sparse and has exactly
283:{\displaystyle kn-\ell }
209:define a graph as being
203:Lee & Streinu (2008)
37:complete bipartite graph
1034:Mathematics of rigidity
911:, IEEE, pp. 1–10,
99:Geiringer–Laman theorem
95:University of Amsterdam
988:Henneberg, L. (1911),
927:10.1109/HICSS.2009.470
601:Henneberg construction
580:
571:Henneberg construction
561:
504:
377:
348:
316:
284:
255:
235:
113:Laman graphs arise in
46:
28:
731:; Servatius, Herman;
578:
562:
505:
445:and reverse the edge.
378:
349:
317:
285:
261:vertices has at most
256:
236:
127:Euclidean congruences
34:
19:
805:Discrete Mathematics
526:
457:
358:
326:
294:
265:
245:
213:
729:Servatius, Brigitte
699:1927ZaMM....7...58P
645:1970JEnMa...4..331L
653:10.1007/BF01534980
585:Lebrecht Henneberg
581:
557:
500:
373:
344:
312:
280:
251:
231:
145:degrees of freedom
47:
29:
975:978-3-95977-124-5
936:978-0-7695-3450-3
725:Santos, Francisco
495:
254:{\displaystyle n}
131:rigidity matroids
1041:
1029:Geometric graphs
1008:
1007:
1001:
993:
985:
979:
978:
967:
947:
941:
939:
920:
904:
898:
896:
879:
870:(8): 1944–1964,
854:
848:
846:
821:
812:(8): 1425–1437,
795:
789:
787:
762:
741:Whiteley, Walter
717:
711:
709:
679:
673:
671:
625:
566:
564:
563:
558:
547:
546:
509:
507:
506:
501:
496:
485:
483:
482:
478:
444:
440:
436:
432:
421:
417:
406:
382:
380:
379:
374:
353:
351:
350:
345:
322:-tight if it is
321:
319:
318:
313:
289:
287:
286:
281:
260:
258:
257:
252:
240:
238:
237:
232:
123:general position
57:are a family of
1049:
1048:
1044:
1043:
1042:
1040:
1039:
1038:
1014:
1013:
1012:
1011:
995:
994:
986:
982:
976:
948:
944:
937:
905:
901:
855:
851:
800:Streinu, Ileana
796:
792:
737:Streinu, Ileana
733:Souvaine, Diane
718:
714:
680:
676:
626:
622:
617:
609:
573:
542:
538:
527:
524:
523:
484:
474:
470:
466:
458:
455:
454:
442:
438:
434:
430:
419:
408:
404:
359:
356:
355:
327:
324:
323:
295:
292:
291:
266:
263:
262:
246:
243:
242:
214:
211:
210:
200:
193:
166:
119:Euclidean plane
115:rigidity theory
111:
103:Hilda Geiringer
44:
12:
11:
5:
1047:
1037:
1036:
1031:
1026:
1024:Graph families
1010:
1009:
980:
974:
942:
935:
899:
849:
790:
753:(1–2): 31–61,
712:
674:
639:(4): 331–340,
619:
618:
616:
613:
607:
597:
596:
593:
572:
569:
556:
553:
550:
545:
541:
537:
534:
531:
512:spanning trees
499:
494:
491:
488:
481:
477:
473:
469:
465:
462:
447:
446:
427:
372:
369:
366:
363:
343:
340:
337:
334:
331:
311:
308:
305:
302:
299:
279:
276:
273:
270:
250:
230:
227:
224:
221:
218:
199:
196:
191:
178:pseudotriangle
165:
162:
110:
107:
69:is a graph on
42:
9:
6:
4:
3:
2:
1046:
1035:
1032:
1030:
1027:
1025:
1022:
1021:
1019:
1005:
999:
991:
984:
977:
971:
966:
961:
957:
953:
946:
938:
932:
928:
924:
919:
914:
910:
903:
895:
891:
887:
883:
878:
873:
869:
865:
864:
859:
853:
845:
841:
837:
833:
829:
825:
820:
815:
811:
807:
806:
801:
798:Lee, Audrey;
794:
786:
782:
778:
774:
770:
766:
761:
756:
752:
748:
747:
742:
738:
734:
730:
726:
722:
716:
708:
704:
700:
696:
692:
688:
684:
678:
670:
666:
662:
658:
654:
650:
646:
642:
638:
634:
630:
624:
620:
612:
606:
602:
594:
591:
590:
589:
586:
577:
568:
551:
548:
543:
539:
535:
529:
521:
517:
513:
492:
489:
486:
479:
475:
471:
467:
460:
452:
428:
425:
424:
423:
415:
411:
401:
399:
395:
394:pseudoforests
391:
387:
386:sparse graphs
370:
367:
364:
361:
338:
335:
332:
306:
303:
300:
277:
274:
271:
268:
248:
225:
222:
219:
208:
204:
195:
190:
187:
186:utility graph
183:
179:
175:
171:
161:
159:
155:
151:
146:
143:
139:
134:
132:
128:
124:
120:
116:
106:
104:
100:
96:
92:
88:
84:
80:
76:
72:
68:
64:
63:rigid systems
60:
59:sparse graphs
56:
52:
41:
38:
33:
27:
23:
22:Moser spindle
18:
989:
983:
955:
945:
908:
902:
877:math/0703921
867:
861:
852:
819:math/0702129
809:
803:
793:
760:math/0307347
750:
744:
715:
693:(1): 58–72,
690:
686:
677:
636:
632:
623:
604:
600:
598:
582:
520:planar graph
516:Network flow
448:
413:
409:
402:
388:, including
201:
188:
167:
157:
153:
149:
141:
137:
135:
112:
91:Gerard Laman
86:
82:
78:
74:
70:
66:
55:Laman graphs
54:
51:graph theory
48:
39:
858:Streinu, I.
451:orientation
290:edges, and
67:Laman graph
1018:Categories
721:Haas, Ruth
615:References
398:arboricity
992:, Leipzig
918:0801.2404
669:122631794
629:Laman, G.
549:
490:
371:ℓ
368:−
339:ℓ
307:ℓ
278:ℓ
275:−
226:ℓ
164:Planarity
93:, of the
998:citation
785:38637747
198:Sparsity
109:Rigidity
77:, every
894:5477763
836:2392060
777:2131802
695:Bibcode
661:0269535
641:Bibcode
588:types:
972:
933:
892:
842:
834:
783:
775:
667:
659:
182:planar
53:, the
913:arXiv
890:S2CID
872:arXiv
840:S2CID
814:arXiv
781:S2CID
755:arXiv
665:S2CID
390:trees
172:is a
121:, in
1004:link
970:ISBN
931:ISBN
844:2826
205:and
35:The
20:The
960:doi
923:doi
882:doi
824:doi
810:308
765:doi
703:doi
649:doi
608:3,3
540:log
487:log
441:to
192:3,3
136:If
49:In
43:3,3
1020::
1000:}}
996:{{
968:,
929:,
921:,
888:,
880:,
868:30
866:,
838:,
832:MR
830:,
822:,
808:,
779:,
773:MR
771:,
763:,
751:31
749:,
739:;
735:;
727:;
701:,
689:,
663:,
657:MR
655:,
647:,
635:,
567:.
400:.
392:,
194:.
168:A
133:.
105:.
1006:)
962::
940:.
925::
915::
897:.
884::
874::
847:.
826::
816::
788:.
767::
757::
710:.
705::
697::
691:7
672:.
651::
643::
637:4
605:K
555:)
552:n
544:3
536:n
533:(
530:O
498:)
493:n
480:2
476:/
472:3
468:n
464:(
461:O
443:u
439:v
435:v
431:u
420:n
416:)
414:n
412:(
410:O
405:n
365:n
362:k
342:)
336:,
333:k
330:(
310:)
304:,
301:k
298:(
272:n
269:k
249:n
229:)
223:,
220:k
217:(
189:K
158:n
154:n
150:n
142:n
138:n
87:n
83:k
79:k
75:k
71:n
40:K
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
