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 sobre 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 grafo tiene exactamente 2 n − 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 planares rígidas. ^[1] Sin embargo, esta caracterización, el teorema de Geiringer-Laman , ya había sido descubierta en 1927 por Hilda Geiringer . ^[2]

Rigidez

Los grafos de Laman surgen en la teoría de la rigidez : si uno coloca los vértices de un grafo de Laman en el plano euclidiano , en la posición general , en general no habrá movimiento continuo simultáneo de todos los puntos, aparte de las congruencias euclidianas , que preserven 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 exactamente 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 2 n grados de libertad en su colocación (cada punto tiene dos coordenadas independientes), pero un grafo rígido tiene solo tres grados de libertad (la posición de uno solo de sus vértices y la rotación del grafo restante 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 2 n − 3 aristas en un grafo de Laman reducen los 2 n grados de libertad de la colocación inicial del punto a los tres grados de libertad de un grafo rígido. Sin embargo, no todo grafo con 2 n − 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 asegura 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.

Planaridad

Una pseudotriangulación puntiaguda es un dibujo de una línea recta plana 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 de menos de 180 grados. Los grafos que se pueden dibujar como pseudotriangulaciones puntiagudas son exactamente los grafos de Laman planares . ^[3] Sin embargo, los grafos de Laman tienen incrustaciones planares que no son pseudotriangulaciones, y hay grafos de Laman que no son planares, como el grafo de utilidad K _3,3 .

Escasez

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

A partir de esta caracterización, es posible reconocer grafos de Laman $de n$ vértices en el tiempo $O (n 2)$ , simulando un "juego de piedras" que comienza con un grafo con $n$ vértices y sin aristas, con dos piedras colocadas en cada vértice, y realiza una secuencia de los siguientes dos tipos de pasos para crear todas las aristas del grafo:

Crea un nuevo borde dirigido que conecte dos vértices que tengan dos guijarros y quita un guijarro del vértice inicial del nuevo borde.
Si un borde apunta desde un vértice $u$ con como máximo una piedra a otro vértice $v$ con al menos una piedra, mueva una piedra de $v$ a $u$ e invierta el borde.

Si estas operaciones se pueden utilizar 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 , basados en probar si duplicar un borde del grafo dado da como resultado un multigrafo que es (2,2)-estrecho (equivalentemente, si se puede descomponer en dos árboles de expansión disjuntos en los bordes ) 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 utilizar para probar si un grafo planar es un grafo de Laman más rápidamente, en tiempo . ^[7] $O(n^{3/2}{\sqrt {\log n}})$ $Estilo de visualización O(n\log ^{3}n)}$

Construcción de Henneberg

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 exactamente los grafos que se pueden obtener, a partir de una sola arista, mediante una secuencia de operaciones de los dos tipos siguientes:

Agrega un nuevo vértice al gráfico, junto con aristas que lo conectan a dos vértices previamente existentes.
Subdivide un borde del gráfico y agrega 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 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 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 opuesto del triángulo.

Referencias

^ Laman, G. (1970), "Sobre los grafos y la rigidez de las estructuras esqueléticas planas", J. Engineering Mathematics , 4 (4): 331–340, Bibcode :1970JEnMa...4..331L, doi :10.1007/BF01534980, MR 0269535, S2CID 122631794.
^ Pollaczek-Geiringer, Hilda (1927), "Über die Gliederung ebener Fachwerke", Zeitschrift für Angewandte Mathematik und Mechanik , 7 (1): 58–72, Bibcode :1927ZaMM....7...58P, doi :10.1002 /zamm.19270070107.
^ Haas, Ruth ; Orden, David; Rote, Günter; Santos, Francisco ; Servatius, Brigitte ; Servatius, Herman; Souvaine, Diane ; Streinu, Ileana ; Whiteley, Walter (2005), "Gráficos mínimamente rígidos planos y pseudo-triangulaciones", Computational Geometry Theory and Applications , 31 (1–2): 31–61, arXiv : math/0307347 , doi :10.1016/j.comgeo.2004.07.003, MR 2131802, S2CID 38637747.
^ Lee, Audrey; Streinu, Ileana (2008), "Algoritmos de juegos de guijarros y gráficos dispersos", Discrete Mathematics , 308 (8): 1425–1437, arXiv : math/0702129 , doi :10.1016/j.disc.2007.07.104, MR 2392060, S2CID 2826.
^ Streinu, I. ; Theran, L. (2009), "Hipergrafos dispersos y algoritmos de juegos de guijarros", European Journal of Combinatorics , 30 (8): 1944–1964, arXiv : math/0703921 , doi :10.1016/j.ejc.2008.12.018, S2CID 5477763.
^ Daescu, O.; Kurdia, A. (2009), "Hacia un algoritmo óptimo para reconocer grafos de Laman", Proc. 42nd Hawaii International Conference on System Sciences (HICSS '09) , IEEE, págs. 1–10, arXiv : 0801.2404 , doi :10.1109/HICSS.2009.470, ISBN 978-0-7695-3450-3.
^ Rollin, Jonathan; Schlipf, Lena; Schulz, André (2019), "Reconocimiento de gráficos planos de Laman", en Bender, Michael A.; Svensson, Ola; Herman, Grzegorz (eds.), 27.º Simposio europeo anual sobre algoritmos (ESA 2019) , Leibniz International Proceedings in Informatics (LIPIcs), vol. 144, Dagstuhl, Alemania: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, págs. 79:1–79:12, doi : 10.4230/LIPIcs.ESA.2019.79 , ISBN 978-3-95977-124-5
^ Henneberg, L. (1911), Die graphische Statik der starren Systeme , Leipzig{{citation}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )