title: Gráfico de Laman
text: # Gráfico de Laman
  
  En la teoría de grafos, los grafos de Laman son una familia de gráficos dispersos que describen los sistemas mínimamente rígidos de varillas y articulaciones en el plano. 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. Los gráficos de Laman llevan el nombre de Gerard Laman, de la Universidad de Amsterdam, quien en 1970 los utilizó para caracterizar estructuras planas rígidas. Esta caracterización, sin embargo, ya había sido descubierta en 1927 por Hilda Geiringer.
  
  ## Rigidez
  
  Los gráficos de Laman surgen en la teoría de la rigidez: si se colocan los vértices de un gráfico de Laman en el plano euclidiano, en posición general, en general no habrá movimiento continuo simultáneo de todos los puntos, aparte de las congruencias euclidianas, que preserva las longitudes de todos los bordes del gráfico. Un grafo es rígido en este sentido si y solo si tiene un subgrafo de Laman que abarca todos sus vértices. Así, los gráficos de Laman son exactamente los gráficos mínimamente rígidos, y forman las bases de las matrices de rigidez bidimensional .
  
  Si se dan n puntos en el plano, entonces hay 2 n grados de libertad en su ubicación (cada punto tiene dos coordenadas independientes), pero un gráfico rígido tiene solo tres grados de libertad (la posición de uno solo de sus vértices y la rotación del gráfico restante alrededor de ese vértice). Intuitivamente, agregar un borde de longitud fija a un gráfico reduce su número de grados de libertad en uno, por lo que el 2 n − 3 aristas en un gráfico de Laman reducen los 2 n grados de libertad de la colocación del punto inicial a los tres grados de libertad de un gráfico rígido. Sin embargo, no todos los gráficos con 2 n − 3 bordes es rígido; la condición en la definición de un gráfico de Laman de que ningún subgráfico puede tener demasiados bordes garantiza que cada borde contribuya a reducir el número total de grados de libertad y no se desperdicie dentro de un subgráfico que ya es rígido debido a sus otros bordes.
  
  ## Planaridad
  
  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. Los gráficos que se pueden dibujar como pseudotriangulaciones puntiagudas son exactamente los gráficos planos de Laman. 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}.$
  
  ## Escasez
  
  Se define un grafo como $(k,\ell )$-disperso si cada subgrafo no vacío con 𝑛 vértices tiene como máximo $kn-\ell$ aristas, y $(k,\ell )$-apretado si es $(k,\ell )$-escaso y tiene exactamente $kn-\ell$ aristas. Por lo tanto, en su notación, los gráficos de Laman son exactamente los gráficos (2,3) ajustados, y los subgráficos de los gráficos de Laman son exactamente los gráficos (2,3) dispersos. 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.
  
  Con base en esta caracterización, es posible reconocer gráficos de Laman de n vértices en el tiempo $O(n^2),$ 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:
  
  * Cree un nuevo borde dirigido que conecte dos vértices que tengan dos guijarros y elimine un guijarro del vértice inicial del nuevo borde.
  * Si una arista apunta desde un vértice u con al menos una piedra a otro vértice v con al menos una piedra, mueva una piedra de v a u e invierta la arista.
  
  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. $O(n^{3/2}{\sqrt {\log n}})$, 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. Las técnicas de flujo de red se pueden usar para probar si un gráfico plano es un gráfico de Laman más rápidamente, en el tiempo. $O(n\log ^{3}n)$.
  
  ## Construcción Henneberg
  
  Antes de la obra de Laman y Geiringer, se caracterizó los gráficos bidimensionales mínimamente rígidos (es decir, los gráficos de Laman) de una manera diferente. Henneberg demostró que los gráficos mínimamente rígidos en dos o más vértices son exactamente los gráficos que se pueden obtener, a partir de un solo borde, mediante una secuencia de operaciones de los siguientes dos tipos:
  
  * Agregue un nuevo vértice al gráfico, junto con los bordes que lo conectan a dos vértices previamente existentes.
  * Subdivida un borde del gráfico y agregue un borde que conecte el vértice recién formado con un tercer vértice previamente existente.
  
  Una secuencia de estas operaciones que forma un gráfico dado se conoce como construcción de Henneberg del gráfico. 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.
  
  