La teoría de grafos topológicos es una rama de la teoría de grafos que estudia la incrustación de gráficos en superficies , la incrustación espacial y los gráficos como espacios topológicos [1] . En esta rama también se estudian las inmersiones gráficas .
Incrustar un gráfico en una superficie significa que queremos dibujar el gráfico en una superficie, como una esfera , sin bordes cruzados . El principal problema de anidamiento, presentado como un rompecabezas matemático , es el problema de “ Casas y pozos ”. Se pueden encontrar aplicaciones más importantes en la preparación de circuitos electrónicos impresos , donde el objetivo es extender (incrustar) circuitos electrónicos (gráficos) en una placa de circuito impreso (superficie) sin cruzar los circuitos para evitar cortocircuitos .
Un gráfico no dirigido puede verse como un complejo simplicial abstracto C , donde los subconjuntos son conjuntos de un elemento (correspondientes a los vértices) y conjuntos de dos elementos (correspondientes a los bordes) [2] . Realización geométrica del complejo | do | consiste en copias del intervalo unitario [0,1] para cada borde, con los extremos de estos intervalos pegados en los vértices. Desde este punto de vista, la incrustación de un gráfico en una superficie o una subdivisión de otro gráfico es un caso especial de incrustación topológica. Un homeomorfismo de grafos es solo una especialización de un homeomorfismo topológico , la noción de un grafo conexo es la misma que una conexión topológica , y un grafo conexo es un árbol si y solo si su grupo fundamental es trivial.
Otros complejos simpliciales asociados con gráficos incluyen los complejos de Whitney o clique , donde los subconjuntos son las cliques del gráfico, y los complejos de coincidencia , donde los subconjuntos son las coincidencias del gráfico (equivalentemente, los complejos clique del complemento del gráfico lineal ). El complejo de emparejamiento de un gráfico bipartito completo se denomina complejo de tablero de ajedrez , ya que puede describirse como un complejo de conjuntos de torres que no se atacan entre sí en un tablero de ajedrez. [3]
John Hopcroft y Robert Tarjan [4] lograron un tiempo promedio para verificar la planaridad de un gráfico que es lineal en el número de aristas. Su algoritmo hace esto mediante la construcción de un gráfico incrustado, al que llaman "palmera". La eficacia de la comprobación de planaridad es fundamental para la visualización de gráficos .
Fan Chang y otros [5] estudiaron el problema de la incrustación de un gráfico con vértices en una línea en el lomo de un libro. Los bordes del gráfico se dibujan en diferentes páginas del libro para que los bordes que se encuentran en la misma página no se crucen. Este problema es una abstracción del problema de diseño de PCB multicapa.
La incrustación de gráficos también se utiliza para demostrar resultados estructurales en gráficos a través de la teoría menor de gráficos y el teorema de estructura de gráficos .