Dibujo de gráficos por capas

El dibujo de grafos en capas o jerárquico es un tipo de dibujo de grafos en el que los vértices de un grafo dirigido se dibujan en filas o capas horizontales con las aristas generalmente dirigidas hacia abajo. ^{[ 1 ] [ 2 ] [ 3 ]} También se conoce como dibujo de grafos estilo Sugiyama, en honor a Kozo Sugiyama , quien desarrolló por primera vez este estilo de dibujo. ^{[ 4 ]}

La forma ideal para un dibujo en capas sería un dibujo planar ascendente , en el que todas las aristas estén orientadas en una dirección consistente y ningún par de aristas se cruce. Sin embargo, los grafos suelen contener ciclos, minimizar el número de aristas con orientación inconsistente es un problema NP- difícil, y minimizar el número de cruces también lo es; por lo tanto, los sistemas de dibujo de grafos en capas suelen aplicar una secuencia de heurísticas que reducen este tipo de defectos en el dibujo sin garantizar encontrar un dibujo con el número mínimo de defectos.

La construcción de un dibujo gráfico por capas se lleva a cabo en una secuencia de pasos:

• Si el grafo de entrada no es ya un grafo dirigido acíclico , se identifica un conjunto de aristas cuya inversión lo convertirá en acíclico. Encontrar el conjunto más pequeño posible de aristas es el problema del conjunto de arcos de retroalimentación NP-completo , por lo que a menudo se utilizan heurísticas voraces en lugar de algoritmos de optimización exactos. ^{[ 1 ] [ 2 ] [ 3 ] [ 5 ] [ 6 ] [ 7 ]} La solución exacta a este problema se puede formular utilizando programación entera . ^{[ 3 ]} Alternativamente, si el número de aristas invertidas es muy pequeño, estas aristas se pueden encontrar mediante un algoritmo tratable con parámetros fijos . ^{[ 8 ]}
• Los vértices del grafo acíclico dirigido resultante del primer paso se asignan a capas, de modo que cada arista va de una capa superior a una inferior. Los objetivos de esta etapa son producir simultáneamente un número pequeño de capas, pocas aristas que abarquen un gran número de capas y una asignación equilibrada de vértices a capas. ^{[ 1 ] [ 2 ] [ 3 ]} Por ejemplo, según el teorema de Mirsky , asignar vértices por capas según la longitud del camino más largo que comienza en cada vértice produce una asignación con el número mínimo posible de capas. ^{[ 1 ] [ 3 ]} El algoritmo de Coffman-Graham puede utilizarse para encontrar una estratificación con un límite predeterminado en el número de vértices por capa y minimizar aproximadamente el número de capas sujeto a esa restricción. ^{[ 1 ] [ 2 ] [ 3 ]} Minimizar el ancho de la capa más ancha es NP-difícil, pero puede resolverse mediante ramificación y corte o aproximarse heurísticamente. ^{[ 3 ]} Alternativamente, el problema de minimizar el número total de capas abarcadas por las aristas (sin límites en el número de vértices por capa) puede resolverse mediante programación lineal . ^{[ 9 ]} Los procedimientos de programación entera , aunque más laboriosos, pueden utilizarse para combinar la minimización de la longitud de las aristas con límites en el número de vértices por nivel. ^{[ 10 ]}
• Las aristas que abarcan varias capas se reemplazan por caminos de vértices ficticios de manera que, después de este paso, cada arista en el grafo expandido conecta dos vértices en capas adyacentes del dibujo. ^{[ 1 ] [ 2 ]}
• Como paso opcional, se puede imponer una capa de vértices concentradores de aristas (o uniones confluentes) entre dos capas de vértices existentes, reduciendo la densidad de aristas al reemplazar subgrafos bipartitos completos por estrellas a través de estos concentradores de aristas. ^{[ 3 ] [ 11 ] [ 12 ]}
• Los vértices dentro de cada capa se permutan en un intento de reducir el número de cruces entre las aristas que la conectan con la capa anterior. ^{[ 1 ] [ 2 ] [ 3 ]} Encontrar el número mínimo de cruces o encontrar un conjunto máximo de aristas sin cruces es NP-completo, incluso cuando se ordena una sola capa a la vez de esta manera, ^{[ 13 ] [ 14 ]} por lo que nuevamente es típico recurrir a heurísticas, como colocar cada vértice en una posición determinada al encontrar el promedio o la mediana de las posiciones de sus vecinos en el nivel anterior y luego intercambiar pares adyacentes siempre que eso mejore el número de cruces. ^{[ 1 ] [ 2 ] [ 9 ] [ 14 ] [ 15 ]} Alternativamente, el ordenamiento de los vértices en una capa a la vez puede elegirse utilizando un algoritmo que sea tratable con parámetros fijos en el número de cruces entre ella y la capa anterior. ^{[ 3 ] [ 16 ]}
• A cada vértice se le asigna una coordenada dentro de su capa, consistente con la permutación calculada en el paso anterior. ^{[ 1 ] [ 2 ]} Las consideraciones en este paso incluyen colocar nodos ficticios en una línea entre sus dos vecinos para evitar curvas innecesarias y colocar cada vértice en una posición centrada con respecto a sus vecinos. ^{[ 3 ]} El trabajo original de Sugiyama propuso una formulación de programación cuadrática de este paso; un método posterior de Brandes y Köpf toma tiempo lineal y garantiza como máximo dos curvas por arista. ^{[ 3 ] [ 17 ]}
• Las aristas invertidas en el primer paso del algoritmo se devuelven a sus orientaciones originales, los vértices ficticios se eliminan del grafo y se dibujan los vértices y las aristas. Para evitar intersecciones entre vértices y aristas, las aristas que abarcan varias capas del dibujo pueden representarse como cadenas poligonales o curvas spline que pasan por cada una de las posiciones asignadas a los vértices ficticios a lo largo de la arista. ^{[ 1 ] [ 2 ] [ 9 ]}

En su forma más simple, los algoritmos de dibujo de grafos por capas pueden requerir un tiempo de O( mn ) en grafos con n vértices y m aristas, debido a la gran cantidad de vértices ficticios que se pueden crear. Sin embargo, para algunas variantes del algoritmo, es posible simular el efecto de los vértices ficticios sin construirlos explícitamente, lo que lleva a una implementación de tiempo casi lineal . ^{[ 18 ]}

La herramienta "punto" en Graphviz produce dibujos por capas. ^{[ 9 ]} También se incluye un algoritmo de dibujo de gráficos por capas en Microsoft Automatic Graph Layout ^{[ 19 ]} y en Tulip . ^{[ 20 ]}

Aunque normalmente se dibujan con vértices en filas y aristas que proceden de arriba a abajo, los algoritmos de dibujo de grafos en capas pueden dibujarse con vértices en columnas y aristas que proceden de izquierda a derecha. ^{[ 21 ]} El mismo marco algorítmico también se ha aplicado a diseños radiales en los que los grafos se organizan en círculos concéntricos alrededor de un nodo inicial ^{[ 3 ] [ 22 ]} y a dibujos tridimensionales en capas de grafos. ^{[ 3 ] [ 23 ]}

En los dibujos de grafos en capas con muchas aristas largas, el desorden de aristas se puede reducir agrupando conjuntos de aristas en haces y enrutándolos juntos a través del mismo conjunto de vértices ficticios. ^{[ 24 ]} De manera similar, para dibujos con muchas aristas que cruzan entre pares de capas consecutivas, las aristas en subgrafos bipartitos máximos se pueden agrupar en haces confluentes. ^{[ 25 ]}

Los dibujos en los que los vértices están dispuestos en capas pueden construirse mediante algoritmos que no siguen el marco de Sugiyama. Por ejemplo, es posible determinar si un grafo no dirigido tiene un dibujo con como máximo k cruces, utilizando h capas, en un tiempo polinomial para cualquier elección fija de k y h , aprovechando el hecho de que los grafos que tienen dibujos de este tipo tienen un ancho de camino acotado . ^{[ 26 ]}

Para dibujos en capas de retículos conceptuales , se puede utilizar un enfoque híbrido que combine el marco de Sugiyama con métodos aditivos (en los que cada vértice representa un conjunto y la posición del vértice es una suma de vectores que representan elementos en el conjunto). En este enfoque híbrido, las fases de permutación de vértices y asignación de coordenadas del algoritmo se reemplazan por una sola fase en la que la posición horizontal de cada vértice se elige como una suma de escalares que representan los elementos de ese vértice. ^{[ 27 ]} Los métodos de dibujo de grafos en capas también se han utilizado para proporcionar una ubicación inicial para algoritmos de dibujo de grafos dirigidos por fuerzas . ^{[ 28 ]}