La teoría de grafos geométricos en sentido amplio es un subcampo grande y amorfo de la teoría de grafos , que se ocupa de los grafos definidos por medios geométricos . En un sentido más estricto, la teoría de grafos geométricos estudia las propiedades combinatorias y geométricas de los grafos geométricos, es decir, los grafos dibujados en el plano euclidiano con aristas rectas que posiblemente se intersecan , y los grafos topológicos , donde se permite que las aristas sean curvas continuas arbitrarias que conectan los vértices ; por lo tanto, puede describirse como "la teoría de grafos geométricos y topológicos" (Pach 2013). Los grafos geométricos también se conocen como redes espaciales .
Un grafo plano rectilíneo es un grafo en el que los vértices están incrustados como puntos en el plano euclidiano y las aristas están incrustadas como segmentos de línea que no se cruzan . El teorema de Fáry establece que cualquier grafo plano puede representarse como un grafo plano rectilíneo. Una triangulación es un grafo plano rectilíneo al que no se le pueden añadir más aristas, llamado así porque cada cara es necesariamente un triángulo; un caso especial de esto es la triangulación de Delaunay , un grafo definido a partir de un conjunto de puntos en el plano conectando dos puntos con una arista siempre que exista un círculo que contenga solo esos dos puntos.
El esqueleto 1- de un poliedro o politopo es el conjunto de vértices y aristas de dicho poliedro o politopo. El esqueleto de cualquier poliedro convexo es un grafo plano, y el esqueleto de cualquier politopo convexo de dimensión k es un grafo k -conexo . Por el contrario, el teorema de Steinitz establece que cualquier grafo plano 3-conexo es el esqueleto de un poliedro convexo; por esta razón, esta clase de grafos también se conoce como grafos poliédricos .
Un grafo euclidiano es un grafo en el que los vértices representan puntos en el plano y a cada arista se le asigna una longitud igual a la distancia euclidiana entre sus extremos. El árbol de expansión mínima euclidiana es el árbol de expansión mínima de un grafo euclidiano completo . También es posible definir grafos por condiciones sobre las distancias; en particular, un grafo de distancia unitaria se forma conectando pares de puntos que están separados por una distancia unitaria en el plano. El problema de Hadwiger–Nelson se ocupa del número cromático de estos grafos.
Un grafo de intersección es un grafo en el que cada vértice está asociado a un conjunto y en el que los vértices están conectados por aristas siempre que los conjuntos correspondientes tengan una intersección no vacía. Cuando los conjuntos son objetos geométricos, el resultado es un grafo geométrico. Por ejemplo, el grafo de intersección de segmentos de línea en una dimensión es un grafo de intervalo ; el grafo de intersección de discos unitarios en el plano es un grafo de disco unitario . El teorema de empaquetamiento de círculos establece que los grafos de intersección de círculos que no se cruzan son exactamente los grafos planares. La conjetura de Scheinerman (probada en 2009) establece que cada grafo planar puede representarse como el grafo de intersección de segmentos de línea en el plano.
Un gráfico de Levi de una familia de puntos y líneas tiene un vértice para cada uno de estos objetos y una arista para cada par de puntos y líneas incidentes. Los gráficos de Levi de configuraciones proyectivas conducen a muchos gráficos y jaulas simétricas importantes .
El gráfico de visibilidad de un polígono cerrado conecta cada par de vértices mediante una arista siempre que el segmento de línea que conecta los vértices se encuentre completamente dentro del polígono. No se sabe cómo comprobar de manera eficiente si un gráfico no dirigido se puede representar como un gráfico de visibilidad.
Un cubo parcial es un grafo cuyos vértices se pueden asociar con los vértices de un hipercubo , de tal manera que la distancia en el grafo es igual a la distancia de Hamming entre los vértices del hipercubo correspondiente. Muchas familias importantes de estructuras combinatorias, como las orientaciones acíclicas de un grafo o las adyacencias entre regiones en una disposición de hiperplano , se pueden representar como grafos de cubo parcial. Un caso especial importante de un cubo parcial es el esqueleto del permutoedro , un grafo en el que los vértices representan permutaciones de un conjunto de objetos ordenados y las aristas representan intercambios de objetos adyacentes en el orden. Varias otras clases importantes de grafos, incluidos los grafos medianos, tienen definiciones relacionadas que involucran incrustaciones métricas (Bandelt y Chepoi 2008).
Un grafo inverso es un grafo formado a partir de las triangulaciones de un conjunto de puntos, en el que cada vértice representa una triangulación y dos triangulaciones están conectadas por una arista si difieren por la sustitución de una arista por otra. También es posible definir grafos inversos relacionados para particiones en cuadriláteros o pseudotriángulos, y para triangulaciones de dimensiones superiores. El grafo inverso de triangulaciones de un polígono convexo forma el esqueleto del asociaedro o politopo de Stasheff . El grafo inverso de las triangulaciones regulares de un conjunto de puntos (proyecciones de envolturas convexas de dimensiones superiores) también se puede representar como un esqueleto, del llamado politopo secundario .
Medios relacionados con Teoría de grafos geométricos en Wikimedia Commons