En geometría computacional y teoría de grafos geométricos , un grafo de línea recta plana (o grafo de línea recta plana , o grafo de línea recta plana ), abreviado PSLG , es una incrustación de un grafo plano en el plano tal que sus aristas se mapean en segmentos de línea recta. [1] El teorema de Fáry (1948) establece que cada grafo plano tiene este tipo de incrustación.
En geometría computacional, las PSLG a menudo se han denominado subdivisiones planas , con la suposición o afirmación de que las subdivisiones son poligonales en lugar de tener límites curvos.
Los PSLG pueden servir como representaciones de varios mapas , por ejemplo, mapas geográficos en sistemas de información geográfica . [2]
Los casos especiales de PSLG son las triangulaciones ( triangulación de polígonos , triangulación de conjuntos de puntos ). Las triangulaciones de conjuntos de puntos son PSLG máximas en el sentido de que es imposible agregarles aristas rectas mientras se mantiene el plano del gráfico. Las triangulaciones tienen numerosas aplicaciones en diversas áreas.
Los PSLG pueden considerarse un tipo especial de grafos euclidianos . Sin embargo, en las discusiones que involucran grafos euclidianos, el interés principal son sus propiedades métricas, es decir, las distancias entre vértices, mientras que para los PSLG el interés principal son las propiedades topológicas. Para algunos grafos, como las triangulaciones de Delaunay , tanto las propiedades métricas como las topológicas son importantes.
Existen tres estructuras de datos conocidas para representar PSLG: la estructura de datos Winged-edge , Halfedge y Quadedge . La estructura de datos Winged-edge es la más antigua de las tres, pero su manipulación a menudo requiere distinciones de casos complicadas. Esto se debe a que las referencias de borde no almacenan la dirección del borde y las direcciones de los bordes alrededor de una cara no necesitan ser consistentes. La estructura de datos Halfedge almacena ambas orientaciones de un borde y las vincula correctamente, simplificando las operaciones y el esquema de almacenamiento. La estructura de datos Quadedge almacena tanto la subdivisión planar como su dual simultáneamente. Sus registros consisten explícitamente solo en registros de borde, cuatro para cada borde, y en una forma simplificada es adecuada para almacenar PSLG. [3]