La teoría geométrica de grafos en sentido amplio es un subcampo extenso y sin límites bien establecidos de la teoría de grafos, que se ocupa de los grafos definido según medios geométricos. En sentido estricto, la teoría geométrica de grafos estudia las propiedades combinatorias y las propiedades métricas de los grafos geométricos, es decir, los grafos dibujados en el plano con aristas rectas que se intersecan; y de los grafos topológicos, donde las aristas pueden ser curvas continuas arbitrarias que conectan los vértices. Por lo tanto, puede describirse como "la teoría de los grafos geométricos y topológicos" (Pach 2013). Los grafos geométricos también se conocen como redes espaciales.

Diferentes tipos de grafos geométricos Un grafo plano de líneas rectas es aquel en el que los vértices están incrustados como puntos en un plano, y las aristas están incrustadas como segmentos que no se cruzan. El teorema de Fáry establece que cualquier grafo plano puede representarse como un grafo plano de líneas rectas. Una triangulación es un grafo plano de líneas rectas al que no se le pueden añadir más aristas, llamado así porque cada cara es necesariamente un triángulo. Un caso especial es la triangulación de Delaunay, un grafo definido a partir de un conjunto de puntos en el plano mediante la conexión de dos puntos con una arista siempre que exista un círculo que contenga únicamente esos dos puntos.

El 1-esqueleto 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-conectado. Recíprocamente, 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 euclídeo es aquel en el que los vértices representan puntos en el plano, y a cada arista se le asigna una longitud igual a la distancia euclídea entre sus extremos. El árbol de expansión mínima euclídea es el árbol recubridor mínimo de un grafo completo euclídeo. También es posible definir grafos mediante condiciones sobre las distancias. En particular, un grafo de distancias unitarias se forma conectando pares de puntos separados por una unidad en el plano. El problema de Hadwiger-Nelson se refiere a la coloración de estos grafos.

Un grafo de intersección es aquel 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 recta en una dimensión es un grafo de intervalos; el grafo de intersección de discos unitarios en el plano es un grafo de disco unidad. El teorema de empaquetamiento de circunferencias establece que los grafos de intersección de círculos que no se cruzan son precisamente los grafos planares. La conjetura de Scheinerman (demostrada en 2009) establece que todo grafo planar puede representarse como el grafo de intersección de segmentos de recta en el plano.

Un grafo 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 punto-línea incidente. Los grafos de Levi de configuración proyectiva dan lugar a muchos grafos simétricos y jaulas importantes.

El grafo de visibilidad de un polígono cerrado conecta cada par de vértices mediante una arista siempre que el segmento de recta que los conecta se encuentre completamente dentro del polígono. Se desconoce cómo comprobar de forma eficiente si un grafo no dirigido puede representarse como un grafo de visibilidad.

Un cubo parcial es un grafo cuyos vértices pueden asociarse con los vértices de un hipercubo, de tal manera que la distancia en el grafo sea igual a la distancia de Hamming entre los vértices correspondientes del hipercubo. Muchas familias importantes de estructuras combinatorias, como las orientaciones acíclicas de un grafo o las adyacencias entre regiones en una disposición en un hiperplano, pueden representarse como grafos de cubo parcial. Un caso especial importante de 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 en el orden de objetos adyacentes. Varias otras clases importantes de grafos, incluidos los grafos medianos, tienen definiciones relacionadas que involucran incrustaciones métricas .

Un grafo volteado 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 en la sustitución de una arista por otra. También es posible definir grafos volteados relacionados para particiones en cuadriláteros o pseudotriángulos, y para triangulaciones de dimensiones superiores. El grafo de inversión de las triangulaciones de un polígono convexo forma el esqueleto del asociaedro o polítopo de Stasheff. El grafo de inversión de la triangulación regular de un conjunto de puntos (proyecciones de envolventes convexas de dimensiones superiores) también puede representarse como un esqueleto del llamado politopo secundario.

Véase también Teoría de grafos topológica Grafo químico Red espacial

Referencias

Bibliografía

Enlaces externos

Teoría de grafos geométricos