Geometric graph theory

Geometric graph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geometric graphs, meaning graphs drawn in the Euclidean plane with possibly intersecting straight-line edges, and topological graphs, where the edges are allowed to be arbitrary continuous curves connecting the vertices; thus, it can be described as "the theory of geometric and topological graphs" (Pach 2013). Geometric graphs are also known as spatial networks.

A planar straight-line graph is a graph in which the vertices are embedded as points in the Euclidean plane, and the edges are embedded as non-crossing line segments. Fáry's theorem states that any planar graph may be represented as a planar straight line graph. A triangulation is a planar straight line graph to which no more edges may be added, so called because every face is necessarily a triangle; a special case of this is the Delaunay triangulation, a graph defined from a set of points in the plane by connecting two points with an edge whenever there exists a circle containing only those two points.

The 1-skeleton of a polyhedron or polytope is the set of vertices and edges of said polyhedron or polytope. The skeleton of any convex polyhedron is a planar graph, and the skeleton of any k-dimensional convex polytope is a k-connected graph. Conversely, Steinitz's theorem states that any 3-connected planar graph is the skeleton of a convex polyhedron; for this reason, this class of graphs is also known as the polyhedral graphs.

Un grafo euclidiano es aquel cuyos 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 mediante condiciones sobre las distancias; en particular, un grafo de distancia unitaria se forma conectando pares de puntos separados por una unidad de distancia en el plano. El problema de Hadwiger-Nelson se refiere al 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 intervalos ; el grafo de intersección de discos unitarios en el plano es un grafo de discos unitarios . El teorema del empaquetamiento de círculos 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) afirma que todo grafo planar puede representarse como el grafo de intersección de segmentos de línea 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 configuraciones proyectivas 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 línea que los une 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 es 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 de hiperplanos , 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 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 flip 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 flip relacionados para particiones en cuadriláteros o pseudotriángulos, y para triangulaciones de dimensiones superiores. El grafo flip de triangulaciones de un polígono convexo forma el esqueleto del asociaedro o politopo de Stasheff . El grafo flip de las triangulaciones regulares de un conjunto de puntos (proyecciones de envolventes convexas de dimensiones superiores) también puede representarse como un esqueleto, del llamado politopo secundario .

• Teoría topológica de grafos
• Gráfico químico
• Red espacial

• Bandelt, Hans-Jürgen; Chepoi, Victor (2008). "Teoría de grafos métricos y geometría: una revisión" (PDF) . Encuestas sobre geometría discreta y computacional: veinte años después . Matemáticas contemporáneas. Vol.  453. Sociedad Matemática Americana. págs. 49–86 . 
• Pach, János , ed. (2004). Hacia una teoría de grafos geométricos . Matemáticas contemporáneas. Vol.  342. Sociedad Matemática Americana.
• Pach, János (2013). "Los inicios de la teoría de grafos geométricos". Centenario de Erdös . Bolyai Soc. Matemáticas. Semental. vol.  25. Budapest: János Bolyai Math. Soc. págs. 465– 484. doi : 10.1007/978-3-642-39286-3_17 . SEÑOR 3203608 .  
• Pisanski, Tomaž ; Randić, Milan (2000). «Puentes entre la geometría y la teoría de grafos» . En Gorini, CA (ed.). Geometría en acción: Artículos sobre geometría aplicada . Washington, DC: Mathematical Association of America. pp. 174–194 . Archivado del original el 27 de septiembre de 2007. 

• Contenido multimedia relacionado con la teoría geométrica de grafos en Wikimedia Commons.