En matemáticas , la teoría de grafos topológicos es una rama de la teoría de grafos . Estudia la incrustación de gráficos en superficies , incrustaciones espaciales de gráficos y gráficos como espacios topológicos . [1] También estudia 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 de incrustación básico 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 y provoquen un cortocircuito .
A un gráfico 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 consta de una copia del intervalo unitario [0,1] por arista, con los puntos finales de estos intervalos pegados en los vértices. Desde este punto de vista, las incrustaciones de gráficos en una superficie o como subdivisiones de otros gráficos son instancias de incrustación topológica, el homeomorfismo de los gráficos es solo la especialización del homeomorfismo topológico , la noción de un gráfico conexo coincide con la conectividad topológica , y un gráfico conexo es un árbol si y sólo si su grupo fundamental es trivial.
Otros complejos simpliciales asociados con gráficos incluyen el complejo de Whitney o complejo de camarilla , con un conjunto por camarilla del gráfico, y el complejo de coincidencia , con un conjunto por coincidencia del gráfico (equivalente, el complejo de camarilla del complemento del gráfico lineal ) . El complejo de emparejamiento de un gráfico bipartito completo se llama complejo de tablero de ajedrez , ya que también puede describirse como el complejo de conjuntos de torres no atacantes en un tablero de ajedrez. [2]
John Hopcroft y Robert Tarjan [3] derivaron un medio para probar la planaridad de un gráfico en el tiempo lineal al número de aristas. Su algoritmo hace esto mediante la construcción de un gráfico integrado al que denominan "palmera". Las pruebas de planaridad eficientes son fundamentales 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 circuito impreso multicapa.
Las incrustaciones de gráficos también se utilizan para demostrar resultados estructurales sobre gráficos, a través de la teoría menor de gráficos y el teorema de la estructura de gráficos .