Dibujo gráfico en capas

El dibujo de gráficos en capas o el dibujo de gráficos jerárquicos es un método de visualización de gráficos en el que los vértices de un gráfico dirigido se dibujan en filas horizontales o capas con bordes predominantemente dirigidos hacia abajo [1] [2] [3] . Esto se conoce como el estilo Sugiyama de visualización de gráficos , en honor a Kozo Sugiyama, quien fue el primero en desarrollar este estilo [4] .

Una forma ideal de dibujo en capas sería el dibujo plano hacia arriba , en el que todos los bordes están orientados en la misma dirección y ningún par de bordes se cruzan. Sin embargo, los gráficos a menudo contienen ciclos, y el problema de minimizar el número de aristas que apuntan en la dirección opuesta es NP-difícil , al igual que el problema de minimizar el número de intersecciones. Por esta razón, los sistemas de representación de gráficos en capas suelen utilizar una secuencia de enfoques heurísticos que reducen este tipo de fallas y encuentran el patrón con la menor cantidad de fallas.

Algoritmo de diseño

La construcción de la visualización de gráficos capa por capa se produce en varias etapas:

• Si el gráfico de entrada aún no es un gráfico acíclico dirigido , se define un conjunto de aristas cuya inversión hace que el gráfico sea acíclico. Encontrar el conjunto de aristas más pequeño posible es un problema NP-completo de encontrar un conjunto de aristas de corte de ciclo , por lo que aquí se usa a menudo un algoritmo heurístico codicioso en lugar de algoritmos de optimización exactos [1] [2] [3] [5] [ 6] [7] . La solución exacta a este problema se puede formular mediante programación entera [3] . Alternativamente, si el número de bordes hacia atrás es muy pequeño, estos bordes se pueden encontrar utilizando un algoritmo de resolución de parámetros fijos [8] .
• Los vértices del gráfico acíclico dirigido obtenido en el primer paso se asignan a capas, de modo que cada arco va de arriba a abajo. El objetivo de este paso es crear una pequeña cantidad de niveles, lograr una pequeña cantidad de bordes que atraviesen una gran cantidad de capas y una asignación equilibrada de vértices en las capas [1] [2] [3] . Por ejemplo, según el teorema de Mirsky , la distribución de vértices por capas según el camino más largo , partiendo del vértice superior, da una distribución con un número mínimo de capas [1] [3] . Puede usar el algoritmo de Coffman-Graham para encontrar una distribución sobre capas con un límite predefinido en la cantidad de vértices por capa y minimizar aproximadamente la cantidad de capas [1] [2] [3] . El problema de minimizar el ancho de la capa más ancha es NP-difícil, pero puede resolverse mediante algoritmos de aproximación heurística o ramificados [3] . Alternativamente, el problema de minimizar el número total de capas abarcadas por los bordes (sin restricciones en el número de vértices en una capa) puede resolverse usando programación lineal [9] . Los procedimientos de programación entera , aunque más costosos en términos de tiempo de cálculo, se pueden utilizar para combinar la minimización de bordes con un límite en el número de vértices por nivel [10] .
• Los bordes que abarcan varias capas se reemplazan con rutas con vértices adicionales, de modo que después de este paso, cada arco en el gráfico expandido conecta dos vértices de capas adyacentes del patrón [1] [2] .
• Como paso adicional (opcional), se puede usar un nivel de concentración de borde (o fusión de intersección) entre dos niveles de vértice existentes para reducir la densidad del arco reemplazando subgráficos bipartitos completos con estrellas a través de estos centros [3] [11] [12] .
• Los vértices dentro de cada capa se reorganizan en un intento de reducir el número de arcos que los conectan con la capa anterior [1] [2] [3] . El problema de encontrar el número mínimo de cruces, o el conjunto máximo de arcos sin cruces, es NP-completo, incluso si estamos tratando de ordenar una capa a la vez [13] [14] , por lo que nuevamente se recurre a la heurística métodos, como colocar cada vértice en una posición determinada por la media o la mediana de las posiciones de los vecinos en el nivel anterior, y luego permutar pares adyacentes hasta que tales permutaciones reduzcan el número de intersecciones [1] [2] [9] [14] [15] . Alternativamente, el orden de los vértices en una capa a la vez puede ser elegido por un algoritmo que se puede resolver de forma paramétrica fija en términos del número de intersecciones entre la capa y la capa anterior [3] [16] .
• A cada vértice se le asigna una coordenada dentro de la capa, lo cual es consistente con el paso anterior [1] [2] . Este paso consiste en insertar vértices adicionales en la línea entre los dos vecinos (para evitar cortes innecesarios ) y colocar cada vértice en una posición central con respecto a los vecinos [3] . El trabajo original de Sugiyama fue formular este paso como un problema de programación cuadrática . El último método de Brandes y Koepf se ejecuta en tiempo lineal y garantiza un máximo de dos rupturas por arco [3] [17] .
• Los arcos invertidos en la primera etapa del algoritmo vuelven a su dirección inicial, los vértices agregados se eliminan del gráfico, después de lo cual se dibujan los vértices y los bordes. Para evitar la intersección entre los vértices y los arcos, los arcos que abarcan varias capas se pueden dibujar como líneas poligonales o como curvas polinómicas por partes a través de vértices adicionales en las capas internas a través de las cuales pasa el arco [1] [2] [9] .

Implementaciones

En su forma más simple, los algoritmos de representación de gráficos en capas pueden tardar O( mn ) en gráficos con n vértices y m aristas, ya que se puede crear una gran cantidad de vértices adicionales. Sin embargo, para algunas variantes del algoritmo, es posible simular el efecto de vértices adicionales sin agregarlos realmente, lo que conduce a la implementación del algoritmo con un tiempo de ejecución casi lineal [18] .

El lenguaje de descripción "DOT" en el paquete Graphviz crea representaciones en capas [9] . El algoritmo de visualización de gráficos en capas también se incluye en la biblioteca de diseño de gráficos automáticos de Microsoft [19] y en el marco Tulip [20] .

Variaciones

Aunque el dibujo generalmente se realiza con vértices en filas y con bordes que van de arriba a abajo, los algoritmos de representación de gráficos en capas pueden organizar los vértices verticalmente en columnas y dibujar bordes de izquierda a derecha [21] . El mismo marco puede usar una disposición radial, donde los vértices están ubicados en círculos concéntricos (centrados en algún nodo inicial) [3] [22] , así como capas de gráficos 3D [3] [23] .

Cuando se visualiza capa por capa de gráficos con una gran cantidad de arcos largos, el caos se puede reducir agrupando conjuntos de bordes en paquetes y dirigiéndolos a través del mismo conjunto de vértices adicionales [24] . Asimismo, para dibujar muchos bordes que se cruzan entre pares de capas sucesivas, los bordes en los subgrafos bipartitos máximos se pueden agrupar en paquetes confluentes [25] .

Las figuras en las que los vértices están dispuestos en capas pueden construirse mediante algoritmos que no siguen el esquema de Sugiyama. Por ejemplo, se puede saber si un gráfico no dirigido tiene una representación con como máximo k intersecciones y h capas en tiempo polinomial para valores fijos de k y h , utilizando el hecho de que los gráficos que tienen representaciones de este tipo tienen un ancho de ruta acotado [ 26 ] .

Para el dibujo capa por capa de celosías conceptuales , se puede utilizar un enfoque híbrido, combinando el enfoque de Sugiyama con métodos aditivos (en los que cada vértice representa un conjunto y la posición del vértice es la suma de los vectores que representan los 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 un solo paso en el que cada posición horizontal de cada vértice se elige como la suma de las representaciones de elementos escalares para ese vértice [27] . Se han utilizado técnicas de visualización de gráficos en capas para proporcionar la ubicación inicial de los algoritmos de visualización de gráficos de potencia [28] .

Notas

1. ↑ 1 2 3 4 5 6 7 8 9 10 Di Battista, Eades et al., 1998 , p. 265–302.
2. ↑ 1 2 3 4 5 6 7 8 9 Bastert, Matuszewski, 2001 , p. 87–120.
3. ↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Healy y Nikolov, 2014 , pág. 409–453.
4. ↑ Sugiyama, Tagawa, Toda, 1981 , pág. 109–125.
5. ↑ Berger y Shor 1990 , pág. 236–243.
6. ↑ Eades, Lin, Smyth, 1993 , pág. 319–323.
7. ↑ Eades, Lin, 1995 , pág. 15–26.
8. ↑ Chen, Liu, Lu et al., 2008 , pág. una.
9. ↑ 1 2 3 4 Gansner, Koutsofios, North, Vo, 1993 , p. 214–230.
10. ↑ Healy, Nikolov, 2002 , pág. 16-30.
11. ↑ Newbery, 1989 , pág. 76–85.
12. ↑ Eppstein, Goodrich, Meng, 2004 , pág. 184–194.
13. ↑ Eades, Whitesides, 1994 , pág. 361–374.
14. ↑ 1 2 Eades, Wormald, 1994 , p. 379–403.
15. ↑ Makinen, 1990 , pág. 175–181.
16. ↑ Dujmovic, Fernau, Kaufmann, 2008 , pág. 313–323.
17. ↑ Brandes, Köpf, 2002 , pág. 31–44.
18. ↑ Eiglsperger, Siebenhaller, Kaufmann, 2005 , pág. 155–166.
19. ↑ Nachmanson, Robertson, Lee, 2008 , pág. 389–394.
20. ↑ Auber, 2004 .
21. ↑ Baburin, 2002 , pág. 366–367.
22. ↑ Bachmaier, 2007 , pág. 583–594.
23. ↑ Hong, Nikolov, 2005 , pág. 69–74.
24. ↑ Pupyrev, Nachmanson, Kaufmann, 2011 , pág. 329–340.
25. ↑ Eppstein, Goodrich, Meng, 2007 , pág. 439–452.
26. ↑ Dujmović, Fellows, Kitching et al., 2008 , p. 267–292.
27. ↑ Cole, 2001 , pág. 47–53.
28. ↑ Schwikowski, Uetz, Fields, 2000 , pág. 1257–126.

Literatura

• Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Dibujos en capas de dígrafos // Dibujo de gráficos: Algoritmos para la visualización de gráficos. - Prentice Hall , 1998. - ISBN 978-0-13-301615-4 .
• Oliver Bastert, Christian Matuszewski. Dibujos en capas de dígrafos // Dibujar gráficos: métodos y modelos. - Springer-Verlag, 2001. - T. 2025. - ( Lecture Notes in Computer Science ). - ISBN 978-3-540-42062-0 . -doi : 10.1007 / 3-540-44969-8_5 .
• Patrick Healy, Nikola S. Nikolov. Dibujo de gráficos jerárquicos // Manual de dibujo y visualización de gráficos / Roberto Tamassia. — Prensa CRC, 2014.
• Kozo Sugiyama, Shôjirô Tagawa, Mitsuhiko Toda. Métodos para la comprensión visual de estructuras de sistemas jerárquicos // IEEE Transactions on Systems, Man, and Cybernetics . - 1981. - T. SMC-11 , núm. 2 . -doi : 10.1109/ TSMC.1981.4308636 .
• Berger B., Shor P. Algoritmos de aproximación para el problema del subgrafo acíclico máximo // Actas del 1er Simposio ACM-SIAM sobre algoritmos discretos (SODA'90) . - 1990. - ISBN 9780898712513 .
• Eades P., Lin X., Smyth WF Una heurística rápida y efectiva para el problema del conjunto de arcos de retroalimentación  // Cartas de procesamiento de información. - 1993. - T. 47 , núm. 6 _ -doi : 10.1016 / 0020-0190(93)90079-O .
• Eades P., Lin X. Una nueva heurística para el problema del conjunto de arcos de retroalimentación // Australian Journal of Combinatorics. - 1995. - T. 12 .
• Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, Igor Razgon. Un algoritmo de parámetros fijos para el problema del conjunto de vértices de retroalimentación dirigida // Journal of the ACM. - 2008. - T. 55 , núm. 5 . -doi : 10.1145/ 1411509.1411511 .
• Gansner ER, Koutsofios E., Carolina del Norte, Vo K.-P. Una técnica para dibujar gráficos dirigidos // IEEE Transactions on Software Engineering. - 1993. - T. 19 , nº. 3 . -doi : 10.1109/ 32.221135 .
• Patrick Healy, Nikola S. Nikolov. Cómo superponer un gráfico acíclico dirigido // Dibujo de gráficos: 9º Simposio internacional, GD 2001 Viena, Austria, 23 al 26 de septiembre de 2001, Documentos revisados. - Springer-Verlag, 2002. - T. 2265. - (Lecture Notes in Computer Science). - ISBN 978-3-540-43309-5 . -doi : 10.1007/ 3-540-45848-4_2 .
• Peter Eades, Sue Whitesides. Dibujo de grafos en dos capas // Informática Teórica. - 1994. - T. 131 , núm. 2 . - doi : 10.1016/0304-3975(94)90179-1 .
• Peter Eades, Nicholas C. Wormald. Cruces de aristas en dibujos de grafos bipartitos // Algorithmica. - 1994. - T. 11 , núm. 4 . -doi : 10.1007/ BF01187020 .
• Concentración Newbery FJ Edge: un método para agrupar gráficos dirigidos // Actas del segundo taller internacional sobre gestión de configuración de software (SCM '89), Princeton, Nueva Jersey, EE . UU . - Asociación de Maquinaria de Computación, 1989. - ISBN 0-89791-334-5 . doi : 10.1145 / 72910.73350 .
• David Eppstein, Michael T. Goodrich, Jeremy Yu Meng. Dibujos en capas confluentes // Proc. 12 Int. Síntoma Dibujo gráfico (GD 2004) / Janos Pach. - Springer-Verlag, 2004. - T. 47. - (Lecture Notes in Computer Science). -doi : 10.1007/ s00453-006-0159-8 .
• Mäkinen E. Experimentos sobre el dibujo de gráficos jerárquicos de 2 niveles // International Journal of Computer Mathematics. - 1990. - T. 36 , núm. 3–4 . -doi : 10.1080/ 00207169008803921 .
• Vida Dujmovic, Henning Fernau, Michael Kaufmann. Revisión de los algoritmos de parámetros fijos para la minimización de cruce unilateral // Journal of Discrete Algorithms. - 2008. - T. 6 , núm. 2 . -doi : 10.1016/ j.jda.2006.12.008 .
• Ulrik Brandes, Boris Köpf. Dibujo gráfico (Viena, 2001). - Berlín: Springer, 2002. - T. 2265 . - ISBN 978-3-540-43309-5 . -doi : 10.1007/ 3-540-45848-4_3 .
• Markus Eiglsperger, Martin Siebenhaller, Michael Kaufmann. 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 al 2 de octubre de 2004, Documentos seleccionados revisados. - Springer-Verlag, 2005. - T. 3383. - (Lecture Notes in Computer Science). — ISBN 978-3-540-24528-5 . -doi : 10.1007 / 978-3-540-31843-9_17 .
• Christian Bachmaier. Una adaptación radial del marco Sugiyama para visualizar información jerárquica // IEEE Transactions on Visualization and Computer Graphics. - 2007. - T. 13 , núm. 3 . -doi : 10.1109/ TVCG.2007.1000 . — PMID 17356223 .
• Lev Nachmanson, George Robertson, Bongshin Lee. Drawing Graphs with GLEE // Graph Drawing, 15th International Symposium, GD 2007, Sydney, Australia, 24 al 26 de septiembre de 2007, Documentos revisados. - Springer-Verlag, 2008. - T. 4875. - (Lecture Notes in Computer Science). — ISBN 978-3-540-77536-2 . -doi : 10.1007 / 978-3-540-77537-9_38 .
• David Auber. Tulip: un gran marco de visualización de gráficos // Software de dibujo de gráficos / Michael Jünger, Petra Mutzel. - Springer-Verlag, 2004. - ISBN 978-3-540-00881-1 .
• Danil E. Baburin. Algunas modificaciones del enfoque de Sugiyama // Graph Drawing, 10th International Symposium, GD 2002, Irvine, CA, EE. UU., 26 al 28 de agosto de 2002, Documentos revisados. - Springer-Verlag, 2002. - T. 2528. - (Lecture Notes in Computer Science). - ISBN 978-3-540-00158-4 . -doi : 10.1007/ 3-540-36151-0_36 .
• Seok-Hee Hong, Nikola S. Nikolov. 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 información (APVis '05) . - 2005. - V. 45. - (Jornadas de Investigación y Práctica en Tecnologías de la Información). — ISBN 9781920682279 .
• Sergey Pupyrev, Lev Nachmanson, Michael Kaufmann. Mejora de los diseños de gráficos en capas con agrupación de bordes // Graph Drawing, 18th International Symposium, GD 2010, Konstanz, Alemania, 21-24 de septiembre de 2010, Documentos seleccionados revisados. - Springer-Verlag, 2011. - T. 6502. - (Lecture Notes in Computer Science). - ISBN 978-3-642-18468-0 . -doi : 10.1007 / 978-3-642-18469-7_30 .
• David Eppstein, Michael T. Goodrich, Jeremy Yu Meng. Dibujos en capas confluentes // Algorithmica. - 2007. - T. 47 , núm. 4 . -doi : 10.1007/ s00453-006-0159-8 . - arXiv : cs/0507051 .
• Dujmović V., Fellows MR, Kitching M., Liotta G., McCartin C., Nishimura N., Ragde P., Rosamond F., Whitesides S. Sobre la complejidad parametrizada del dibujo de gráficos en capas // Algorithmica . - 2008. - T. 52 , núm. 2 . -doi : 10.1007/ s00453-007-9151-1 .
• Ricardo Cole. Diseño automatizado de retículas conceptuales utilizando diagramas en capas y diagramas aditivos // Australian Computer Science Communications. - 2001. - T. 23 , núm. 1 . — ISBN 0-7695-0963-0 . -doi : 10.1109/ ACSC.2001.906622 .
• Benno Schwikowski, Peter Uetz, Stanley Fields. Una red de interacciones proteína-proteína en levadura // Nature Biotechnology. - 2000. - T. 18 , núm. 12 _ -doi : 10.1038/ 82360 . —PMID 11101803 .