En matemáticas , la teoría de grafos topológicos es una rama de la teoría de grafos . Estudia la incrustación de grafos en superficies , las incrustaciones espaciales de grafos y los grafos como espacios topológicos . [1] También estudia las inmersiones de grafos.
Incrustar un gráfico en una superficie significa que queremos dibujar el gráfico en una superficie, una esfera por ejemplo, sin que dos aristas se crucen. Un problema básico de incrustación que a menudo se presenta como un rompecabezas matemático es el problema de las tres utilidades . Se pueden encontrar otras aplicaciones en la impresión de circuitos electrónicos , donde el objetivo es imprimir (incrustar) un circuito (el gráfico) en una placa de circuito (la superficie) sin que dos conexiones se crucen entre sí y resulten en un cortocircuito .
A un grafo no dirigido podemos asociar un complejo simplicial abstracto C con un conjunto de un solo elemento por vértice y un conjunto de dos elementos por arista. La realización geométrica | C | del complejo consiste en una copia del intervalo unitario [0,1] por arista, con los puntos finales de estos intervalos pegados entre sí en los vértices. En esta visión, las incrustaciones de grafos en una superficie o como subdivisiones de otros grafos son ambas instancias de incrustación topológica, el homeomorfismo de grafos es simplemente la especialización del homeomorfismo topológico , la noción de grafo conexo coincide con la conectividad topológica , y un grafo conexo es un árbol si y solo si su grupo fundamental es trivial.
Otros complejos simpliciales asociados con grafos incluyen el complejo de Whitney o complejo de camarilla , con un conjunto por camarilla del grafo, y el complejo de emparejamiento , con un conjunto por emparejamiento del grafo (equivalentemente, el complejo de camarilla del complemento del grafo lineal ). El complejo de emparejamiento de un grafo bipartito completo se denomina complejo de tablero de ajedrez , ya que también se puede describir como el complejo de conjuntos de torres no atacantes en un tablero de ajedrez. [2]
John Hopcroft y Robert Tarjan [3] desarrollaron un método para probar la planaridad de un gráfico en un tiempo lineal al número de aristas. Su algoritmo lo hace construyendo una incrustación de gráfico que denominan "palmera". La prueba eficiente de planaridad es fundamental para el dibujo de gráficos .
Fan Chung et al [4] estudiaron el problema de incrustar un gráfico en un libro con los vértices del gráfico en una línea a lo largo del lomo del libro. Sus bordes se dibujan en páginas separadas de tal manera que los bordes que residen en la misma página no se cruzan. Este problema abstrae los problemas de diseño que surgen en el enrutamiento de placas de circuitos impresos multicapa.
Las incrustaciones de gráficos también se utilizan para demostrar resultados estructurales sobre gráficos, a través de la teoría de gráficos menores y el teorema de estructura de gráficos .