Incrustaciones simultáneas

La incrustación simultánea es una técnica de dibujo de grafos y visualización de información que permite visualizar dos o más grafos diferentes en conjuntos de vértices etiquetados iguales o superpuestos , evitando cruces dentro de ambos grafos. Se permiten cruces entre una arista de un grafo y una arista del otro. ^{[ 1 ]}

Si se permite dibujar los bordes como polilíneas o curvas , entonces cualquier grafo planar puede dibujarse sin cruzarse con sus vértices en posiciones arbitrarias en el plano, donde la misma colocación de vértices proporciona una incrustación simultánea. ^{[ 1 ]}

Hay dos modelos restringidos: incrustación geométrica simultánea, donde cada grafo debe dibujarse planarmente con segmentos de línea que representen sus aristas en lugar de curvas más complejas, restringiendo los dos grafos dados a subclases de los grafos planares, e incrustación simultánea con aristas fijas, donde se permiten curvas o dobleces en las aristas, pero cualquier arista en ambos grafos debe estar representada por la misma curva en ambos dibujos. ^{[ 1 ]} En el modelo no restringido, cualquier par de grafos planares puede tener una incrustación simultánea.

La incrustación simultánea es una técnica de dibujo de grafos y visualización de información que permite visualizar dos o más grafos diferentes en conjuntos de vértices etiquetados iguales o superpuestos , evitando cruces dentro de ambos grafos. Se permiten cruces entre una arista de un grafo y una arista del otro; solo se prohíben los cruces entre dos aristas del mismo grafo. ^{[ 1 ]}

Si se permite dibujar las aristas como polilíneas o curvas , entonces cualquier grafo planar puede dibujarse sin cruces con sus vértices en posiciones arbitrarias en el plano. Usar la misma ubicación de vértices para dos grafos proporciona una incrustación simultánea de ambos. La investigación se ha centrado en encontrar dibujos con pocas curvas o con pocos cruces entre las aristas de los dos grafos. ^{[ 1 ]}

Existen dos modelos restringidos: la incrustación geométrica simultánea y la incrustación simultánea con aristas fijas, donde se permiten curvas o dobleces en las aristas, pero cualquier arista presente en ambos gráficos debe estar representada por la misma curva en ambos dibujos. Cuando existe una incrustación geométrica simultánea, automáticamente también es una incrustación simultánea con aristas fijas. ^{[ 1 ]}

Para problemas de incrustación simultánea en más de dos grafos, es habitual suponer que todos los pares de grafos de entrada tienen la misma intersección entre sí; es decir, los conjuntos de aristas y vértices de los grafos forman un girasol . Esta restricción se conoce como intersección de girasol . ^{[ 1 ]}

La incrustación simultánea está estrechamente relacionada con el grosor , el número mínimo de subgrafos planares que pueden cubrir todas las aristas de un grafo dado, y el grosor geométrico, el número mínimo de colores de arista necesarios en un dibujo en línea recta de un grafo dado sin cruces entre aristas del mismo color. En particular, el grosor de un grafo dado es dos, si las aristas del grafo se pueden particionar en dos subgrafos que tienen una incrustación simultánea, y el grosor geométrico es dos, si las aristas se pueden particionar en dos subgrafos con incrustación geométrica simultánea. ^{[ 2 ]}

En la incrustación geométrica simultánea, cada grafo debe representarse como un grafo planar con segmentos de línea que representen sus aristas, en lugar de curvas más complejas, lo que restringe los dos grafos dados a subclases de los grafos planares. Muchos resultados sobre incrustación geométrica simultánea se basan en la idea de que las coordenadas cartesianas de los vértices de los dos grafos dados pueden derivarse de propiedades de ambos. Uno de los resultados más básicos de este tipo es que cualquier par de grafos de caminos sobre el mismo conjunto de vértices siempre tienen una incrustación simultánea. Para hallar dicha incrustación, se puede usar la posición de un vértice en el primer camino como su coordenada x , y la posición del mismo vértice en el segundo camino como su coordenada y . De esta manera, el primer camino se representará como una polilínea monótona en x , un tipo de curva que automáticamente no se autocruza, y el segundo camino se representará de forma similar como una polilínea monótona en y .

Este tipo de dibujo coloca los vértices en una red entera de dimensiones lineales en los tamaños del grafo. Diseños definidos de manera similar también funcionan, con tamaños de cuadrícula más grandes pero aún lineales, cuando ambos grafos son orugas o cuando ambos son grafos cíclicos . Una incrustación simultánea en una cuadrícula de dimensiones lineales también es posible para cualquier número de grafos que sean todos estrellas . Otros pares de tipos de grafos que siempre admiten una incrustación simultánea, pero que podrían necesitar tamaños de cuadrícula más grandes, incluyen un grafo rueda y un grafo cíclico, un árbol y un emparejamiento , o un par de grafos que tienen ambos un grado máximo de dos. Sin embargo, pares de grafos planares y un emparejamiento, o de un Angelini, Geyer, Neuwirth y Kaufmann demostraron que existen un árbol y un camino, que no tienen incrustación geométrica simultánea. ^{[ 3 ] [ 4 ]}

Probar si dos grafos admiten una incrustación geométrica simultánea es NP-difícil . ^{[ 1 ] [ 5 ]} Más precisamente, es completo para la teoría existencial de los reales . La demostración de este resultado también implica que para algunos pares de grafos que tienen incrustaciones geométricas simultáneas, la cuadrícula más pequeña en la que se pueden dibujar tiene un tamaño doblemente exponencial. ^{[ 6 ] [ 2 ]} Cuando existe una incrustación geométrica simultánea, automáticamente también es una incrustación simultánea con aristas fijas. ^{[ 1 ]}

En la incrustación simultánea con aristas fijas, se permiten curvas o dobleces en las aristas, pero cualquier arista presente en ambos grafos debe estar representada por la misma curva en ambos dibujos. ^{[ 1 ]} La clasificación de los diferentes tipos de entrada como siempre con una incrustación o como a veces no posible depende no solo de los dos tipos de grafos a dibujar, sino también de la estructura de su intersección. Por ejemplo, siempre es posible encontrar dicha incrustación cuando ambos grafos dados son grafos exteriores planares y su intersección es un bosque lineal , con como máximo un doblez por arista y con coordenadas de vértice y puntos de doblez que pertenecen a una cuadrícula de área polinómica. Sin embargo, existen otros pares de grafos exteriores planares con intersecciones más complejas que no tienen dicha incrustación. También es posible encontrar una incrustación simultánea con aristas fijas para cualquier par de un grafo planar y un árbol. ^{[ 7 ] [ 8 ] [ 9 ]}

Es una cuestión abierta si la existencia de una incrustación simultánea con aristas fijas para dos grafos dados puede probarse en tiempo polinomial . Sin embargo, para tres o más grafos, el problema es NP-completo . Cuando existen incrustaciones simultáneas con aristas fijas, pueden encontrarse en tiempo polinomial para pares de grafos exteriores planares y para grafos biconexos , es decir, pares de grafos cuya intersección es biconexa. ^{[ 1 ] [ 10 ] [ 11 ] [ 12 ]}

Cualquier par de grafos planares puede tener una incrustación simultánea. Esto puede hacerse en una cuadrícula de área polinómica, con como máximo dos curvaturas por arista. Cualquier par de grafos subhamiltonianos tiene una incrustación simultánea con como máximo una curvatura por arista. ^{[ 1 ] [ 8 ] [ 13 ]}