La teoría de grafos geométricos en el sentido más amplio es un subcampo grande y amorfo de la teoría de grafos , que se ocupa de los gráficos 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, gráficos dibujados en el plano euclidiano con aristas rectas posiblemente intersectadas , y gráficas topológicas , donde se permite que las aristas sean curvas continuas arbitrarias que conectan los vértices ; por tanto, puede describirse como "la teoría de los grafos geométricos y topológicos" (Pach 2013). Los gráficos geométricos también se conocen como redes espaciales .
Un gráfico plano de línea recta es un gráfico 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 gráfico plano se puede representar como un gráfico plano de línea recta. Una triangulación es un gráfico plano de línea recta al que no se le pueden agregar 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 gráfico 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 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 gráfico plano, y el esqueleto de cualquier politopo convexo de k dimensiones es un gráfico k conexo . Por el contrario, el teorema de Steinitz establece que cualquier gráfico plano de 3 conexos es el esqueleto de un poliedro convexo; por esta razón, esta clase de gráficas también se conoce como gráficas poliédricas .
Un gráfico euclidiano es un gráfico en el que los vértices representan puntos en el plano y a cada borde se le asigna una longitud igual a la distancia euclidiana entre sus puntos finales. El árbol de expansión mínimo euclidiano es el árbol de expansión mínimo de un gráfico euclidiano completo . También es posible definir gráficas por condiciones de las distancias; en particular, un gráfico de distancia unitaria se forma conectando pares de puntos que están separados por una unidad de distancia en el plano. El problema de Hadwiger-Nelson se refiere al número cromático de estos gráficos.
Un gráfico de intersección es un gráfico en el que cada vértice está asociado con 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 gráfico geométrico. Por ejemplo, el gráfico de intersección de segmentos de línea en una dimensión es un gráfico de intervalo ; la gráfica de intersección de discos unitarios en el plano es una gráfica de disco unitario . El teorema del empaquetamiento de círculos establece que las gráficas de intersección de círculos que no se cruzan son exactamente gráficas planas. La conjetura de Scheinerman (probada en 2009) establece que cada gráfico plano se puede representar como el gráfico de intersección de segmentos de línea en el plano.
Una gráfica 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 punto-línea incidente. Los gráficos de Levi de configuraciones proyectivas conducen a muchos gráficos y jaulas simétricos importantes .
El gráfico de visibilidad de un polígono cerrado conecta cada par de vértices mediante un borde siempre que el segmento de línea que conecta los vértices se encuentre completamente en el polígono. No se sabe cómo probar de manera eficiente si un gráfico no dirigido se puede representar como un gráfico de visibilidad.
Un cubo parcial es un gráfico cuyos vértices se pueden asociar con los vértices de un hipercubo , de tal manera que la distancia en el gráfico es igual a la distancia de Hamming entre los vértices del hipercubo correspondientes. Muchas familias importantes de estructuras combinatorias, como las orientaciones acíclicas de un gráfico o las adyacencias entre regiones en una disposición de hiperplano , se pueden representar como gráficos cúbicos parciales. Un caso especial importante de un cubo parcial es el esqueleto del permutoedro , un gráfico 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 gráficos, incluidos los gráficos de medianas, tienen definiciones relacionadas que involucran incorporaciones métricas (Bandelt y Chepoi 2008).
Un flip graph es un gráfico 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 se diferencian por la sustitución de una arista por otra. También es posible definir gráficos de inversión relacionados para particiones en cuadriláteros o pseudotriángulos, y para triangulaciones de dimensiones superiores. El flipgraph de triangulaciones de un polígono convexo forma el esqueleto del asociaedro o politopo de Stasheff . El flip-graph de las triangulaciones regulares de un conjunto de puntos (proyecciones de cascos convexos de dimensiones superiores) también se puede representar como un esqueleto del llamado politopo secundario .
Medios relacionados con la teoría de grafos geométricos en Wikimedia Commons