Laman Graph

A Laman graph is a graph satisfying Laman's theorem. In other words, it is a graph 👁 G
have exactly 👁 2n-3
graph edges, where 👁 n
is the number of graph vertices in 👁 G
and for which 👁 e^'<=2n^'-3
for every subgraph of 👁 G
having 👁 n^'
graph vertices and 👁 e^'
graph edges. The singleton graph 👁 K_1
is generally taken to be a Laman graph by convention, even though it does not satisfy the condition 👁 e=2n-3
.

Laman graphs are always connected.

The numbers of simple Laman graphs on 👁 n=1
, 2, ... nodes are 1, 1, 1, 1, 3, 13, 70, 608, 7222, 110132, 2039273, 44176717, 1092493042, ... (OEIS A227117).

Laman graphs are minimally rigid, in the sense that removing any edge makes the resulting graph flexible when placed "in general position." Laman graphs form the bases of the so-called two-dimensional rigidity matroids, which are describe the number of degrees of freedom of an undirected graph with rigid edges of fixed lengths.

Laman graphs are "generically" rigid in 👁 R^2
. In other words, they are rigid for embeddings with vertices in general position. However, a Laman graph may have flexible embeddings corresponding to vertices satisfying constraints of lower dimension. For example, an embedding of the utility graph 👁 K_(3,3)
, which is a Laman graph, is rigid in the plane unless its six vertices lie on a conic (Bolker and Roth 1980, Maehara 1992).

Flexible embeddings of Laman graphs can commonly arise when incrementally removing sets of vertices from an initially rigid graph having a fair degree of symmetry.

See also

Braced Polygon, Laman's Theorem, Rigid Graph, Triangulated Graph

Explore with Wolfram|Alpha

References

Bolker, E. D. and Roth, B. "When is a Bipartite Graph a Rigid Framework?" Pacific J. Math. 90, 27-44, 1980.Capco, J.; Gallet, M.; Grasegger, G.; Koutschan, C.; Lubbes, N.; and Schicho, J. "The Number of Realizations of a Laman Graph." https://arxiv.org/abs/1701.05500. Nov. 2017.Daescu, O. and Kurdia, A. "Towards an Optimal Algorithm for Recognizing Laman Graphs." In Proc. 42nd Hawaii International Conference on System Sciences (HICSS '09). IEEE, pp. 1-10, 2009. https://arxiv.org/abs/0801.2404.Henneberg, L. Die graphische Statik der starren Systeme. Leipzig, Germany: 1911.Laman, G. "On Graphs and Rigidity of Plane Skeletal Structures." J. Engineering Math. 4, 331-340, 1970.Maehara, H. "Distance Graphs in Euclidean Space." Ryukyu Math. J. 5, 33-51, 1992.Pollaczek-Geiringer, H. "Über die Gliederung ebener Fachwerke." Zeitschr. f. Angewandte Math. u. Mechanik 7, 58-72, 1992.Sloane, N. J. A. Sequence A227117 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Laman Graph

Cite this as:

Weisstein, Eric W. "Laman Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/LamanGraph.html

Subject classifications