Teoría topológica de grafos

En matemáticas , la teoría topológica de grafos 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 grafo en una superficie significa dibujarlo sobre una superficie, por ejemplo una esfera , sin que dos aristas se crucen. Un problema básico de incrustación, a menudo presentado como un rompecabezas matemático , es el problema de las tres utilidades . Otras aplicaciones se encuentran en la impresión de circuitos electrónicos, donde el objetivo es imprimir (incrustar) un circuito (el grafo) en una placa de circuitos (la superficie) sin que dos conexiones se crucen y provoquen un cortocircuito .

A un grafo no dirigido podemos asociar un complejo simplicial abstracto C con un conjunto de un 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 extremos de estos intervalos unidos en los vértices. Desde esta perspectiva, las incrustaciones de grafos en una superficie o como subdivisiones de otros grafos son 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 conexidad topológica , y un grafo conexo es un árbol si y solo si su grupo fundamental es trivial.

Otros complejos simpliciales asociados a grafos incluyen el complejo de Whitney o complejo de clique , con un conjunto por cada clique del grafo, y el complejo de emparejamiento , con un conjunto por cada emparejamiento del grafo (o, equivalentemente, el complejo de clique del complemento del grafo de líneas ). El complejo de emparejamiento de un grafo bipartito completo se denomina complejo de tablero de ajedrez , ya que también puede describirse como el complejo de conjuntos de torres que no atacan en un tablero de ajedrez. ^{[ 2 ]}

John Hopcroft y Robert Tarjan ^{[ 3 ]} desarrollaron un método para probar la planaridad de un grafo en un tiempo lineal al número de aristas. Su algoritmo lo logra mediante la construcción de una incrustación del grafo que denominan "árbol de palmeras". La prueba eficiente de planaridad es fundamental para el dibujo de grafos .

Fan Chung et al . ^{[ 4 ]} estudiaron el problema de incrustar un grafo en un libro con los vértices del grafo alineados a lo largo del lomo. Sus aristas se dibujan en páginas separadas, de manera que las aristas que se encuentran en la misma página no se crucen. Este problema abstrae los problemas de diseño que surgen en el enrutamiento de placas de circuitos impresos multicapa.

Las incrustaciones de grafos también se utilizan para demostrar resultados estructurales sobre grafos, a través de la teoría de menores de grafos y el teorema de estructura de grafos .

• Número de cruce (teoría de grafos)
• Género
• Grafo planar
• Árbol real
• Gráfico toroidal
• Combinatoria topológica
• Gráfico de voltaje