Formalmente, un grafo de Laman es un grafo de n vértices tal que, para todo k, cada subgrafo de k vértices tiene como máximo 2 k − 3 aristas, y tal que todo el gráfico tiene exactamente 2 n − 3 bordes.[1] Esta caracterización, sin embargo, ya había sido descubierta en 1927 por Hilda Geiringer.Un grafo es rígido en este sentido si y solo si tiene un subgrafo de Laman que abarca todos sus vértices.Una pseudotriangulación puntiaguda es un dibujo en línea recta plana de un gráfico, con las propiedades de que la cara exterior es convexa, que cada cara delimitada es un pseudotriángulo, un polígono con solo tres vértices convexos, y que las aristas incidentes en cada vértice abarcan un ángulo de menos de 180 grados.[3] Sin embargo, los gráficos de Laman tienen incrustaciones planas que no son pseudotriangulaciones y hay gráficos de Laman que no son planos, como el gráfico de utilidad K 3,3.La misma notación se puede usar para describir otras familias importantes de gráficos dispersos, incluidos árboles, pseudobosques y gráficos de arboricidad acotada.[4][5] Con base en esta caracterización, es posible reconocer gráficos de Laman de n vértices en el tiempo O(n2), simulando un "juego de guijarros" que comienza con un gráfico con n vértices y sin bordes, con dos guijarros colocados en cada vértice, y realiza una secuencia de los siguientes dos tipos de pasos para crear todos los bordes del gráfico: Si estas operaciones se pueden usar para construir una orientación del gráfico dado, entonces es necesariamente (2,3)-disperso y viceversa.Sin embargo, son posibles algoritmos más rápidos, que se ejecutan en el tiempo., basado en probar si duplicar un borde del gráfico dado da como resultado un multigrafo que es (2,2) ajustado (equivalentemente, si se puede descomponer en dos árboles de expansión disjuntos) y luego usar esta descomposición para verificar si el gráfico dado es un gráfico de Laman.Por ejemplo, el gráfico bipartito completo K 3,3 se puede formar usando la primera operación para formar un triángulo y luego aplicando la segunda operación para subdividir cada borde del triángulo y conectar cada punto de subdivisión con el vértice del triángulo opuesto.
