En geometría computacional y teoría geométrica de grafos, un grafo de líneas rectas plano (PSLG por sus siglas en inglés), también llamado grafo plano de líneas rectas, es una representación embebida de un grafo plano en un plano, de tal manera que sus aristas se transforman en segmentos de línea recta. El teorema de Fáry (1948) afirma que todo grafo plano posee este tipo de incrustación.
En geometría computacional, estos grafos se han denominado a menudo subdivisiones planas, asumiendo que las subdivisiones son poligonales en lugar de tener límites curvos.
Pueden servir como representaciones de diversos mapas, por ejemplo, para la cartografía en los sistemas de información geográfica.
Casos especiales son las triangulaciones (la triangulación de un polígono o la triangulación de conjuntos de puntos). Las triangulaciones de conjuntos de puntos son grafos de líneas rectas planos maximales, en el sentido de que es imposible añadirles aristas rectas manteniendo el grafo planar. Las triangulaciones tienen numerosas aplicaciones en diversas áreas.
También pueden considerarse un tipo especial de grafos euclídeos. Sin embargo, en discusiones sobre grafos euclídeos, el interés principal reside en sus propiedades métricas, es decir, las distancias entre vértices, mientras que con carácter más general su interés principal reside en las propiedades topológicas. Para algunos grafos, como la triangulación de Delaunay, tanto las propiedades métricas como las topológicas son importantes.
Representaciones Existen tres estructuras de datos bien conocidas para representar grafos de líneas rectas planos: aristas con alas, aristas dobles y aristas cuádruples. La estructura de datos de arista alada es la más antigua de las tres, pero su manipulación suele requerir distinciones complejas entre casos. Esto se debe a que las referencias a las aristas no almacenan la dirección de la arista, y las direcciones de las aristas alrededor de una cara no tienen por qué ser consistentes. La estructura de datos de aristas dobles almacena ambas orientaciones de una arista y las enlaza correctamente, simplificando las operaciones y el esquema de almacenamiento. La estructura de datos de aristas cuádruples almacena simultáneamente la subdivisión planar y su dual. Sus registros consisten explícitamente solo en registros de aristas, cuatro por cada arista, y en una forma simplificada es adecuada para almacenar grafos de líneas rectas planos.Handbook of Data Structures and Applications, D. P. Mehta and S. Sahni, 2005, , chapter 17
Problemas en términos de grafos de líneas rectas planos Ubicación de un punto: para un punto de consulta, determinar a qué cara del grafo de líneas rectas plano pertenece.
Superposición de mapas: hallar la superposición de dos grafos de líneas rectas planos (mapas), que consiste en la subdivisión del plano mediante los dos grafos de líneas rectas planos incrustados simultáneamente. En sistemas de información geográfica, este problema se conoce como "superposición de mapas temáticos".
Véase también Lista de aristas doblemente conectadas, una estructura de datos para representar un PSLG Tamaño de la característica local
Referencias
Categoría:Algoritmos geométricos Categoría:Grafos geométricos Categoría:Grafos planares