Gráfico de Laman

En teoría de grafos , los grafos de Laman son una familia de grafos dispersos que describen los sistemas mínimamente rígidos de barras y articulaciones en el plano. Formalmente, un grafo de Laman es un grafo en${\displaystyle n}$vértices tales que, para todo${\displaystyle k\geq 2}$, cada${\displaystyle k}$-el subgrafo de vértices tiene como máximo${\displaystyle 2k-3}$bordes, y de tal manera que todo el grafo tenga exactamente${\displaystyle 2n-3}$aristas. Los grafos de Laman reciben su nombre de Gerard Laman , de la Universidad de Ámsterdam , quien en 1970 los utilizó para caracterizar estructuras planas rígidas. ^{[ 1 ]} Sin embargo, esta caracterización, el teorema de Geiringer-Laman , ya había sido descubierta en 1927 por Hilda Geiringer . ^{[ 2 ]}

Los grafos de Laman surgen en la teoría de la rigidez : si se colocan los vértices de un grafo de Laman en el plano euclidiano , en posición general , no habrá, en general, ningún movimiento continuo simultáneo de todos los puntos, aparte de las congruencias euclidianas , que preserve las longitudes de todas las aristas del grafo. Un grafo es rígido en este sentido si y solo si tiene un subgrafo de Laman que abarca todos sus vértices. Por lo tanto, los grafos de Laman son precisamente los grafos mínimamente rígidos y forman las bases de los matroides de rigidez bidimensionales .

Si se dan n puntos en el plano, entonces hay 2n grados de libertad en su ubicación (cada punto tiene dos coordenadas independientes), pero un grafo rígido tiene solo tres grados de libertad (la posición de uno de sus vértices y la rotación del resto del grafo alrededor de ese vértice). Intuitivamente, agregar una arista de longitud fija a un grafo reduce su número de grados de libertad en uno, por lo que las 2n − 3 aristas en un grafo de Laman reducen los 2n grados de libertad de la ubicación inicial de los puntos a los tres grados de libertad de un grafo rígido. Sin embargo, no todo grafo con 2n − 3 aristas es rígido; la condición en la definición de un grafo de Laman de que ningún subgrafo puede tener demasiadas aristas garantiza que cada arista contribuya a reducir el número total de grados de libertad y no se desperdicie dentro de un subgrafo que ya es rígido debido a sus otras aristas.    

Una pseudotriangulación puntiaguda es un dibujo plano de línea recta de un grafo, con las propiedades de que la cara exterior es convexa, que cada cara acotada es un pseudotriángulo , un polígono con solo tres vértices convexos, y que las aristas incidentes a cada vértice abarcan un ángulo menor de 180 grados. Los grafos que se pueden dibujar como pseudotriangulaciones puntiagudas son precisamente los grafos de Laman planos . ^{[ 3 ]} Sin embargo, los grafos de Laman tienen incrustaciones planas que no son pseudotriangulaciones, y hay grafos de Laman que no son planos, como el grafo de utilidad K _3,3 .

Lee y Streinu (2008) y Streinu y Theran (2009) definen un gráfico como${\displaystyle (k,\ell )}$-disperso si cada subgrafo no vacío con${\displaystyle n}$vértices tiene como máximo${\displaystyle kn-\ell }$bordes y${\displaystyle (k,\ell )}$-apretado si lo es${\displaystyle (k,\ell )}$-escaso y tiene exactamente${\displaystyle kn-\ell }$aristas. Por lo tanto, en su notación, los grafos de Laman son exactamente los grafos (2,3)-apretados, y los subgrafos de los grafos de Laman son exactamente los grafos (2,3)-dispersos. La misma notación puede usarse para describir otras familias importantes de grafos dispersos , incluyendo árboles , pseudobosques y grafos de arboricidad acotada . ^{[ 4 ] [ 5 ]}

Basándonos en esta caracterización, es posible reconocer grafos de Laman de n vértices en tiempo O ( n ² ) , simulando un "juego de guijarros" que comienza con un grafo con n vértices y sin aristas, con dos guijarros colocados en cada vértice, y realiza una secuencia de los dos tipos de pasos siguientes para crear todas las aristas del grafo:

• Crea una nueva arista dirigida que conecte dos vértices cualesquiera que tengan dos guijarros cada uno, y elimina un guijarro del vértice inicial de la nueva arista.
• Si una arista apunta desde un vértice u con como máximo una piedrecita a otro vértice v con al menos una piedrecita, mueva una piedrecita de v a u e invierta la arista.

Si estas operaciones se pueden usar para construir una orientación del grafo dado, entonces es necesariamente (2,3)-disperso, y viceversa. Sin embargo, son posibles algoritmos más rápidos, que se ejecutan en tiempo${\displaystyle O(n^{3/2}{\sqrt {\log n}})}$, basado en probar si duplicar una arista del grafo dado resulta en un multigrafo que es (2,2)-ajustado (equivalentemente, si se puede descomponer en dos árboles de expansión disjuntos en aristas ) y luego usar esta descomposición para verificar si el grafo dado es un grafo de Laman. ^{[ 6 ]} Las técnicas de flujo de red se pueden usar para probar si un grafo planar es un grafo de Laman más rápidamente, en tiempo${\displaystyle O(n\log ^{3}n)}$. ^{[ 7 ]}

Antes del trabajo de Laman y Geiringer, Lebrecht Henneberg caracterizó los grafos mínimamente rígidos bidimensionales (es decir, los grafos de Laman) de una manera diferente. ^{[ 8 ]} Henneberg demostró que los grafos mínimamente rígidos en dos o más vértices son precisamente los grafos que se pueden obtener, partiendo de una sola arista, mediante una secuencia de operaciones de los dos tipos siguientes:

1. Agrega un nuevo vértice al grafo, junto con las aristas que lo conectan a dos vértices previamente existentes.
2. Subdivide una arista del grafo y añade una arista que conecte el vértice recién formado con un tercer vértice preexistente.

Una secuencia de estas operaciones que forma un grafo determinado se conoce como construcción de Henneberg del grafo. Por ejemplo, el grafo bipartito completo K _3,3 se puede formar utilizando la primera operación para crear un triángulo y luego aplicando la segunda operación para subdividir cada arista del triángulo y conectar cada punto de subdivisión con el vértice opuesto del triángulo.