Dibujo de gráficos en capas

Dibujo de gráficos con vértices en capas horizontales

Dibujo en capas de un gráfico acíclico dirigido producido por Graphviz

El dibujo de gráficos en capas o dibujo de gráficos jerárquicos es un tipo de dibujo de gráficos en el que los vértices de un gráfico dirigido se dibujan en filas o capas horizontales con los bordes generalmente dirigidos hacia abajo. ^{[1] [2] [3]} También se conoce como dibujo de gráficos al 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 plano ascendente , en el que todos los bordes están orientados en una dirección consistente y ningún par de bordes se cruza. Sin embargo, los grafos a menudo contienen ciclos, minimizar el número de bordes orientados de manera inconsistente es NP-hard , y minimizar el número de cruces también es NP-hard; por lo tanto, los sistemas de dibujo de grafos en capas generalmente aplican una secuencia de heurísticas que reducen este tipo de fallas en el dibujo sin garantizar encontrar un dibujo con el número mínimo de fallas.

Algoritmo de diseño

La construcción de un dibujo gráfico en capas se realiza en una secuencia de pasos:

• Si el gráfico de entrada no es ya un gráfico acíclico dirigido , se identifica un conjunto de aristas cuya inversión lo hará acíclico. Encontrar el conjunto de aristas más pequeño posible es el problema del conjunto de arcos de retroalimentación NP-completo , por lo que a menudo se utilizan aquí 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 manejable 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 una pequeña cantidad de capas, pocas aristas que abarquen una gran cantidad de capas y una asignación equilibrada de vértices a capas. ^{[1] [2] [3]} Por ejemplo, por el teorema de Mirsky , asignar vértices por capas según la longitud del camino más largo que comienza desde cada vértice produce una asignación con el mínimo número posible de capas. ^{[1] [3]} El algoritmo de Coffman-Graham se puede utilizar para encontrar una estratificación con un límite predeterminado en la cantidad de vértices por capa y minimizar aproximadamente la cantidad de capas sujetas a esa restricción. ^{[1] [2] [3]} Minimizar el ancho de la capa más ancha es NP-hard pero se puede resolver mediante ramificación y corte o aproximarse heurísticamente. ^[3] Como alternativa, el problema de minimizar el número total de capas abarcadas por los bordes (sin ningún límite en el número de vértices por capa) se puede resolver utilizando programación lineal . ^{[9] Los procedimientos} de programación entera , aunque requieren más tiempo, se pueden utilizar para combinar la minimización de la longitud de los bordes con límites en el número de vértices por nivel. ^[10]
• Los bordes que abarcan varias capas se reemplazan por rutas de vértices ficticios de modo que, después de este paso, cada borde en el gráfico 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 los bordes 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 bordes 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 orden de los vértices en una capa a la vez puede elegirse utilizando un algoritmo que sea manejable con parámetros fijos en el número de cruces entre esta 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 borde. ^{[3] [17]}
• Las aristas invertidas en el primer paso del algoritmo vuelven a sus orientaciones originales, los vértices ficticios se eliminan del gráfico 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 se pueden dibujar 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]}

Implementaciones

En su forma más simple, los algoritmos de dibujo de grafos en capas pueden requerir tiempo 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 conduce a una implementación en tiempo casi lineal . ^[18]

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

Variaciones

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

En dibujos de gráficos en capas con muchos bordes largos, el desorden de bordes se puede reducir agrupando conjuntos de bordes en haces y enrutándolos juntos a través del mismo conjunto de vértices ficticios. ^[24] De manera similar, para dibujos con muchos bordes que se cruzan entre pares de capas consecutivas, los bordes 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 una cantidad de tiempo que es polinómica para cualquier elección fija de k y h , utilizando el hecho de que los grafos que tienen dibujos de este tipo tienen un ancho de camino acotado . ^[26]

Para los dibujos en capas de redes conceptuales , se puede utilizar un enfoque híbrido que combina 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 única fase en la que la posición horizontal de cada vértice se elige como una suma de escalares que representan los elementos para ese vértice. ^[27] Los métodos de dibujo de gráficos en capas también se han utilizado para proporcionar una ubicación inicial para algoritmos de dibujo de gráficos dirigidos por fuerza . ^[28]

Referencias

1. Di Battista, Giuseppe; Eades, Pedro ; Tamasia, Roberto ; Tollis, Ioannis G. (1998), "Dibujos en capas de dígrafos", Dibujo de gráficos: algoritmos para la visualización de gráficos , Prentice Hall , págs. 265–302, ISBN 978-0-13-301615-4.
2. Bastert, Oliver; Matuszewski, Christian (2001), "Dibujos en capas de dígrafos", en Kaufmann, Michael; Wagner, Dorothea (eds.), Dibujo de gráficos: métodos y modelos , Lecture Notes in Computer Science , vol. 2025, Springer-Verlag, págs. 87–120, doi :10.1007/3-540-44969-8_5, ISBN 978-3-540-42062-0.
3. Healy, Patrick; Nikolov, Nikola S. (2014), "Dibujo de gráficos jerárquicos", en Tamassia, Roberto (ed.), Manual de dibujo y visualización de gráficos, CRC Press, págs. 409–453.
4. Sugiyama, Kozo; Tagawa, Shôjirô; Toda, Mitsuhiko (1981), "Métodos para la comprensión visual de estructuras de sistemas jerárquicos", IEEE Transactions on Systems, Man, and Cybernetics , SMC-11 (2): 109–125, doi :10.1109/TSMC.1981.4308636, MR  0611436, S2CID  8367756.
5. Berger, B. ; Shor, P. (1990), "Algoritmos de aproximación para el problema del subgrafo acíclico máximo", Actas del 1.er Simposio ACM-SIAM sobre algoritmos discretos (SODA'90), págs. 236-243, ISBN 9780898712513.
6. Eades, P .; Lin, X.; Smyth, WF (1993), "Una heurística rápida y eficaz para el problema del conjunto de arcos de retroalimentación", Information Processing Letters , 47 (6): 319–323, doi :10.1016/0020-0190(93)90079-O.
7. Eades, P .; Lin, X. (1995), "Una nueva heurística para el problema del arco de retroalimentación", Australian Journal of Combinatorics , 12 : 15-26.
8. Chen, Jianer; Liu, Yang; Lu, Songjian; O'Sullivan, Barry; Razgon, Igor (2008), "Un algoritmo de parámetros fijos para el problema del conjunto de vértices con retroalimentación dirigida", Journal of the ACM , 55 (5): 1, doi :10.1145/1411509.1411511, S2CID  1547510.
9. Gansner, ER; Koutsofios, E.; North, SC; Vo, K.-P. (1993), "Una técnica para dibujar gráficos dirigidos", IEEE Transactions on Software Engineering , 19 (3): 214–230, doi :10.1109/32.221135.
10. Healy, Patrick; Nikolov, Nikola S. (2002), "Cómo superponer un gráfico acíclico dirigido", Graph Drawing: 9th International Symposium, GD 2001 Vienna, Austria, 23-26 de septiembre de 2001, Documentos revisados , Lecture Notes in Computer Science, vol. 2265, Springer-Verlag, págs. 16-30, doi : 10.1007/3-540-45848-4_2 , ISBN 978-3-540-43309-5, Sr.  1962416.
11. Newbery, FJ (1989), "Concentración de bordes: un método para agrupar gráficos dirigidos", Actas del 2º Taller internacional sobre gestión de configuración de software (SCM '89), Princeton, Nueva Jersey, EE. UU. , Association for Computing Machinery, págs. 76–85, doi : 10.1145/72910.73350 , ISBN 0-89791-334-5, Número de identificación del sujeto  195722969.
12. Eppstein, David ; Goodrich, Michael T. ; Meng, Jeremy Yu (2007), "Dibujos en capas confluentes", en Pach, János (ed.), Dibujos en capas confluentes , Lecture Notes in Computer Science, vol. 47 (3383 ed.), Springer-Verlag, págs. 184–194, arXiv : cs.CG/0507051 , doi :10.1007/s00453-006-0159-8, S2CID  1169.
13. Eades, Peter ; Whitesides, Sue (1994), "Dibujar gráficos en dos capas", Theoretical Computer Science , 131 (2): 361–374, doi : 10.1016/0304-3975(94)90179-1.
14. Eades, Peter ; Wormald, Nicholas C. (1994), "Cruces de aristas en dibujos de grafos bipartitos", Algorithmica , 11 (4): 379–403, doi :10.1007/BF01187020, S2CID  22476033.
15. Mäkinen, E. (1990), "Experimentos sobre el dibujo de gráficos jerárquicos de dos niveles", International Journal of Computer Mathematics , 36 (3–4): 175–181, doi :10.1080/00207169008803921.
16. Dujmović, Vida ; Fernau, Henning; Kaufmann, Michael (2008), "Revisión de algoritmos de parámetros fijos para la minimización de cruces unilaterales", Journal of Discrete Algorithms , 6 (2): 313–323, doi : 10.1016/j.jda.2006.12.008 , MR  2418986.
17. Brandes, Ulrik ; Köpf, Boris (2002), "Asignación de coordenadas horizontales rápida y sencilla", Dibujo de gráficos (Viena, 2001) , Lecture Notes in Computer Science, vol. 2265, Berlín: Springer, págs. 31–44, doi : 10.1007/3-540-45848-4_3 , ISBN 978-3-540-43309-5, Sr.  1962417.
18. Eiglsperger, Markus; Siebenhaller, Martin; Kaufmann, Michael (2005), "Una implementación eficiente del algoritmo de Sugiyama para el dibujo de gráficos en capas", Graph Drawing, 12th International Symposium, GD 2004, Nueva York, NY, EE. UU., 29 de septiembre-2 de octubre de 2004, Documentos seleccionados revisados , Lecture Notes in Computer Science, vol. 3383, Springer-Verlag, págs. 155-166, doi : 10.1007/978-3-540-31843-9_17 , ISBN 978-3-540-24528-5.
19. Nachmanson, Lev; Robertson, George; Lee, Bongshin (2008), "Dibujo de gráficos con GLEE" (PDF) , en Hong, Seok-Hee ; Nishizeki, Takao ; Quan, Wu (eds.), Dibujo de gráficos, 15.º Simposio internacional, GD 2007, Sídney, Australia, 24-26 de septiembre de 2007, Documentos revisados ​​, Lecture Notes in Computer Science, vol. 4875, Springer-Verlag, págs. 389-394, doi : 10.1007/978-3-540-77537-9_38 , ISBN 978-3-540-77536-2.
20. Auber, David (2004), "Tulip: un marco de visualización de gráficos enorme", en Jünger, Michael; Mutzel, Petra (eds.), Software de dibujo gráfico , Springer-Verlag, ISBN 978-3-540-00881-1.
21. Baburin, Danil E. (2002), "Algunas modificaciones del enfoque de Sugiyama", Graph Drawing, 10th International Symposium, GD 2002, Irvine, CA, EE. UU., 26-28 de agosto de 2002, Documentos revisados , Lecture Notes in Computer Science, vol. 2528, Springer, págs. 366-7, doi : 10.1007/3-540-36151-0_36 , ISBN 978-3-540-00158-4.
22. Bachmaier, Christian (2007), "Una adaptación radial del marco de Sugiyama para visualizar información jerárquica", IEEE Transactions on Visualization and Computer Graphics , 13 (3): 583–594, doi :10.1109/TVCG.2007.1000, PMID  17356223, S2CID  9852297.
23. Hong, Seok-Hee ; Nikolov, Nikola S. (2005), "Dibujos en capas de gráficos dirigidos en tres dimensiones", Actas del Simposio de Asia y el Pacífico de 2005 sobre visualización de la información (APVis '05), Conferencias sobre investigación y práctica en tecnología de la información, vol. 45, págs. 69–74, ISBN 9781920682279.
24. Pupyrev, Sergey; Nachmanson, Lev; Kaufmann, Michael (2011), "Mejora de los diseños de gráficos en capas con agrupamiento de aristas", Graph Drawing, 18.º Simposio Internacional, GD 2010, Konstanz, Alemania, 21-24 de septiembre de 2010, Documentos seleccionados revisados , Lecture Notes in Computer Science, vol. 6502, Springer, págs. 329–340, doi : 10.1007/978-3-642-18469-7_30 , ISBN 978-3-642-18468-0.
25. Eppstein, David ; Goodrich, Michael T. ; Meng, Jeremy Yu (2007), "Dibujos en capas confluentes", Algorithmica , 47 (4): 439–452, arXiv : cs/0507051 , doi :10.1007/s00453-006-0159-8, S2CID  1169.
26. Dujmović, V .; Fellows, MR; Kitching, M.; Liotta, G.; McCartin, C.; Nishimura, N.; Ragde, P.; Rosamond, F.; Whitesides, S. (2008), "Sobre la complejidad parametrizada del dibujo de gráficos en capas", Algorithmica , 52 (2): 267–292, doi :10.1007/s00453-007-9151-1, S2CID  2298634.
27. Cole, Richard (2001). "Diseño automatizado de redes conceptuales mediante diagramas en capas y diagramas aditivos". Actas de la 24.ª Conferencia Australiana de Ciencias Informáticas. ACSC 2001. Vol. 23. págs. 47–53. doi :10.1109/ACSC.2001.906622. ISBN 0-7695-0963-0.S2CID 7143873  .
28. Benno Schwikowski; Peter Uetz y Stanley Fields (2000). "Una red de interacciones proteína-proteína en levadura". Nature Biotechnology . 18 (12): 1257–61. doi :10.1038/82360. PMID  11101803. S2CID  3009359.