Un dibujo de un gráfico o diagrama de red es una representación pictórica de los vértices y aristas de un gráfico. Este dibujo no debe confundirse con el gráfico en sí: a un mismo gráfico pueden corresponder diseños muy diferentes. [2] En abstracto, lo único que importa es qué pares de vértices están conectados por aristas. Sin embargo, en concreto, la disposición de estos vértices y aristas dentro de un dibujo afecta su comprensibilidad, usabilidad, costo de fabricación y estética . [3] El problema empeora si el gráfico cambia con el tiempo agregando y eliminando aristas (dibujo de gráfico dinámico) y el objetivo es preservar el mapa mental del usuario. [4]
Convenciones gráficas
Gráfico dirigido con puntas de flecha que muestran las direcciones de los bordes
Los grafos se dibujan frecuentemente como diagramas de nodos-enlaces en los que los vértices se representan como discos, cajas o etiquetas textuales y los bordes se representan como segmentos de línea , polilíneas o curvas en el plano euclidiano . [3] Los diagramas de nodos-enlaces se remontan a las obras de los siglos XIV al XVI de Pseudo-Lull que se publicaron bajo el nombre de Ramon Llull , un polímata del siglo XIII. Pseudo-Lull dibujó diagramas de este tipo para grafos completos con el fin de analizar todas las combinaciones por pares entre conjuntos de conceptos metafísicos. [5]
En el caso de los gráficos dirigidos , las puntas de flecha forman una convención gráfica comúnmente utilizada para mostrar su orientación ; [2] sin embargo, los estudios de usuarios han demostrado que otras convenciones como el estrechamiento proporcionan esta información de manera más efectiva. [6] El dibujo plano ascendente utiliza la convención de que cada borde está orientado desde un vértice inferior a un vértice superior, lo que hace que las puntas de flecha sean innecesarias. [7]
Las convenciones alternativas a los diagramas de nodo-enlace incluyen representaciones de adyacencia como empaquetamientos circulares , en los que los vértices están representados por regiones disjuntas en el plano y los bordes están representados por adyacencias entre regiones; representaciones de intersección en las que los vértices están representados por objetos geométricos no disjuntos y los bordes están representados por sus intersecciones; representaciones de visibilidad en las que los vértices están representados por regiones en el plano y los bordes están representados por regiones que tienen una línea de visión sin obstáculos entre sí; dibujos confluentes, en los que los bordes se representan como curvas suaves dentro de vías de tren matemáticas ; tejidos, en los que los nodos se representan como líneas horizontales y los bordes como líneas verticales; [8] y visualizaciones de la matriz de adyacencia del gráfico.
Medidas de calidad
Se han definido muchas medidas de calidad diferentes para los dibujos de gráficos, en un intento de encontrar medios objetivos para evaluar su estética y facilidad de uso. [9] Además de guiar la elección entre diferentes métodos de diseño para el mismo gráfico, algunos métodos de diseño intentan optimizar directamente estas medidas.
El número de cruces de un dibujo es el número de pares de aristas que se cruzan entre sí. Si el gráfico es plano , entonces suele ser conveniente dibujarlo sin ninguna intersección de aristas; es decir, en este caso, un dibujo de gráfico representa una incrustación de gráfico . Sin embargo, los gráficos no planos surgen con frecuencia en las aplicaciones, por lo que los algoritmos de dibujo de gráficos generalmente deben permitir cruces de aristas. [10]
El área de un dibujo es el tamaño de su cuadro delimitador más pequeño , en relación con la distancia más cercana entre dos vértices. Los dibujos con un área más pequeña son generalmente preferibles a los de un área más grande, porque permiten que las características del dibujo se muestren en un tamaño mayor y, por lo tanto, de manera más legible. La relación de aspecto del cuadro delimitador también puede ser importante.
La visualización de simetrías es el problema de encontrar grupos de simetría dentro de un gráfico determinado y encontrar un dibujo que muestre la mayor cantidad posible de simetría. Algunos métodos de diseño conducen automáticamente a dibujos simétricos; por el contrario, algunos métodos de dibujo comienzan por encontrar simetrías en el gráfico de entrada y las utilizan para construir un dibujo. [11]
Es importante que los bordes tengan formas lo más simples posibles, para que sea más fácil seguirlos a simple vista. En los dibujos de polilíneas, la complejidad de un borde se puede medir por su número de curvas , y muchos métodos apuntan a proporcionar dibujos con pocas curvas totales o pocas curvas por borde. De manera similar, para las curvas spline, la complejidad de un borde se puede medir por el número de puntos de control en el borde.
Varias medidas de calidad de uso común se refieren a las longitudes de los bordes: por lo general, es deseable minimizar la longitud total de los bordes, así como la longitud máxima de cualquier borde. Además, puede ser preferible que las longitudes de los bordes sean uniformes en lugar de muy variadas.
La resolución angular es una medida de los ángulos más agudos en el dibujo de un gráfico. Si un gráfico tiene vértices con un grado alto , entonces necesariamente tendrá una resolución angular pequeña, pero la resolución angular puede limitarse por debajo mediante una función del grado. [12]
El número de pendiente de un grafo es el número mínimo de pendientes de aristas distintas necesarias en un dibujo con aristas de segmentos de línea recta (permitiendo cruces). Los grafos cúbicos tienen un número de pendiente de cuatro como máximo, pero los grafos de grado cinco pueden tener un número de pendiente ilimitado; queda abierto si el número de pendiente de los grafos de grado 4 está acotado. [12]
Métodos de diseño
Una visualización de red basada en fuerzas. [13]Visualización del diseño del gráfico espectral.
Existen muchas estrategias de diseño de gráficos diferentes:
En los sistemas de diseño basados en fuerzas , el software de dibujo de gráficos modifica la ubicación inicial de un vértice moviendo continuamente los vértices de acuerdo con un sistema de fuerzas basado en metáforas físicas relacionadas con sistemas de resortes o mecánica molecular . Por lo general, estos sistemas combinan fuerzas atractivas entre vértices adyacentes con fuerzas repulsivas entre todos los pares de vértices, con el fin de buscar un diseño en el que las longitudes de los bordes sean pequeñas mientras que los vértices estén bien separados. Estos sistemas pueden realizar una minimización basada en el descenso de gradiente de una función de energía , o pueden traducir las fuerzas directamente en velocidades o aceleraciones para los vértices en movimiento. [14]
Métodos de diseño ortogonal, que permiten que los bordes del gráfico se extiendan horizontal o verticalmente, paralelos a los ejes de coordenadas del diseño. Estos métodos fueron diseñados originalmente para problemas de diseño de PCB y VLSI , pero también se han adaptado para el dibujo de gráficos. Por lo general, implican un enfoque multifase en el que se planariza un gráfico de entrada reemplazando los puntos de cruce por vértices, se encuentra una incrustación topológica del gráfico planarizado, se eligen las orientaciones de los bordes para minimizar las curvas, se colocan los vértices de manera consistente con estas orientaciones y, finalmente, una etapa de compactación del diseño reduce el área del dibujo. [16]
Algoritmos de diseño de árboles: estos muestran una formación similar a un árbol con raíces, adecuada para árboles . A menudo, en una técnica llamada "diseño de globos", los hijos de cada nodo del árbol se dibujan en un círculo que rodea el nodo, con los radios de estos círculos disminuyendo en los niveles inferiores del árbol para que estos círculos no se superpongan. [17]
Los métodos de dibujo de grafos en capas (a menudo denominados dibujo al estilo Sugiyama) son los más adecuados para grafos acíclicos dirigidos o grafos que son casi acíclicos, como los grafos de dependencias entre módulos o funciones en un sistema de software. En estos métodos, los nodos del grafo se organizan en capas horizontales utilizando métodos como el algoritmo Coffman-Graham , de tal manera que la mayoría de los bordes van hacia abajo de una capa a la siguiente; después de este paso, los nodos dentro de cada capa se organizan de manera de minimizar los cruces. [18]
Diagrama de arco
Los diagramas de arco , un estilo de diseño que se remonta a la década de 1960, [19] colocan vértices en una línea; los bordes se pueden dibujar como semicírculos por encima o por debajo de la línea, o como curvas suaves unidas entre sí a partir de múltiples semicírculos.
Los métodos de diseño circular colocan los vértices del gráfico en un círculo, eligiendo cuidadosamente el orden de los vértices alrededor del círculo para reducir los cruces y colocar los vértices adyacentes cerca unos de otros. Los bordes se pueden dibujar como cuerdas del círculo o como arcos dentro o fuera del círculo. En algunos casos, se pueden utilizar múltiples círculos. [20]
El dibujo de dominancia coloca los vértices de tal manera que un vértice esté hacia arriba, hacia la derecha o hacia ambos lados del otro si y solo si es alcanzable desde el otro vértice. De esta manera, el estilo de diseño hace que la relación de alcanzabilidad del gráfico sea visualmente evidente. [21]
Dibujos de gráficos específicos de la aplicación
Los gráficos y dibujos de gráficos que surgen en otras áreas de aplicación incluyen
Además, los pasos de colocación y enrutamiento de la automatización del diseño electrónico (EDA) son similares en muchos aspectos al dibujo de gráficos, al igual que el problema de la incrustación voraz en la computación distribuida , y la literatura sobre el dibujo de gráficos incluye varios resultados tomados de la literatura de EDA. Sin embargo, estos problemas también difieren en varios aspectos importantes: por ejemplo, en EDA, la minimización del área y la longitud de la señal son más importantes que la estética, y el problema de enrutamiento en EDA puede tener más de dos terminales por red, mientras que el problema análogo en el dibujo de gráficos generalmente solo involucra pares de vértices para cada borde.
^ Di Battista et al. (1998), págs. vii–viii; Herman, Melançon y Marshall (2000), Sección 1.1, "Áreas de aplicación típicas".
^ ab Di Battista y col. (1998), pág. 6.
^ ab Di Battista y col. (1998), pág. viii.
^ Misue y otros (1995).
^ Knuth (2013).
^ Holten y van Wijk (2009); Holten et al. (2011).
^ Garg y Tamassia (1995).
^ "La vida es un sueño".
^ Di Battista et al. (1998), Sección 2.1.2, Estética, págs. 14-16; Purchase, Cohen y James (1997).
^ Di Battista y col. (1998), pág.14.
^ Di Battista y col. (1998), pág. 16.
^ desde Pach y Sharir (2009).
^ Grandjean (2014).
^ Di Battista et al. (1998), Sección 2.7, "El enfoque dirigido por la fuerza", págs. 29-30, y Capítulo 10, "Métodos dirigidos por la fuerza", págs. 303-326.
^ Beckman (1994); Koren (2005).
^ Di Battista y col. (1998), Capítulo 5, "Flujo y dibujos ortogonales", págs. 137-170; Eiglsperger, Fekete y Klau (2001).
^ Herman, Melançon y Marshall (2000), Sección 2.2, "Diseño tradicional: una descripción general".
^ Sugiyama, Tagawa y Toda (1981); Bastert y Matuszewski (2001); Di Battista et al. (1998), Capítulo 9, "Dibujos en capas de dígrafos", págs.
^ Saaty (1964).
^ Doğrusöz, Madden y Madden (1997).
^ Di Battista y col. (1998), Sección 4.7, "Planos de dominancia", págs.
^ Scott (2000); Brandes, Freeman y Wagner (2014).
^ Di Battista et al. (1998), págs. 15-16, y Capítulo 6, "Flujo y planaridad ascendente", págs. 171-214; Freese (2004).
^ Zapponi (2003).
^ Anderson y Head (2006).
^ Di Battista y Rimondini (2014).
^ Bachmaier, Brandes y Schreiber (2014).
^ "Graphviz y Dynagraph: herramientas de dibujo de gráficos estáticos y dinámicos", por John Ellson, Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North y Gordon Woodhull, en Jünger & Mutzel (2004).
^ "Introducción al dibujo de gráficos", Wolfram Language & System Documentation Center , consultado el 21 de marzo de 2024
^ Nachmanson, Robertson y Lee (2008).
^ "Tulip: un enorme marco de visualización de gráficos", por David Auber, en Jünger & Mutzel (2004).
^ "yFiles: visualización y diseño automático de gráficos", por Roland Wiese, Markus Eiglsperger y Michael Kaufmann, en Jünger & Mutzel (2004).
^ Tantau (2013); véase también la presentación anterior de GD 2012 Archivado el 27 de mayo de 2016 en Wayback Machine.
Herman, Ivan; Melançon, Guy; Marshall, M. Scott (2000), "Visualización gráfica y navegación en la visualización de información: una encuesta", IEEE Transactions on Visualization and Computer Graphics , 6 (1): 24–43, doi :10.1109/2945.841119.
Anderson, James Andrew; Head, Thomas J. (2006), Teoría de autómatas con aplicaciones modernas, Cambridge University Press, págs. 38-41, ISBN 978-0-521-84887-9.
Bachmaier, Christian; Brandes, Ulrik ; Schreiber, Falk (2014), "Redes biológicas", en Tamassia, Roberto (ed.), Manual de dibujo y visualización de gráficos , CRC Press, págs. 621–651.
Bastert, Oliver; Matuszewski, Christian (2001), "Dibujos en capas de dígrafos", en Kaufmann, Michael; Wagner, Dorothea (eds.), Dibujo de grafos: 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.
Beckman, Brian (1994), Teoría del diseño de gráficos espectrales, Informe técnico MSR-TR-94-04, Microsoft Research, archivado desde el original el 1 de abril de 2016 , consultado el 17 de septiembre de 2011.
Di Battista, Giuseppe; Rimondini, Massimo (2014), "Computer Networks", en Tamassia, Roberto (ed.), Manual de visualización y dibujo de gráficos , CRC Press, págs..
Eiglsperger, Markus; Fekete, Sándor; Klau, Gunnar (2001), "Dibujo de grafos ortogonales", en Kaufmann, Michael; Wagner, Dorothea (eds.), Drawing Graphs , Lecture Notes in Computer Science, vol. 2025, Springer Berlin / Heidelberg, págs. 121–171, doi :10.1007/3-540-44969-8_6, ISBN 978-3-540-42062-0.
Freese, Ralph (2004), "Automated lattice drawing", en Eklund, Peter (ed.), Concept Lattices: Second International Conference on Formal Concept Analysis, ICFCA 2004, Sydney, Australia, 23-26 de febrero de 2004, Actas (PDF) , Lecture Notes in Computer Science, vol. 2961, Springer-Verlag, págs. 589–590, CiteSeerX 10.1.1.69.6245 , doi :10.1007/978-3-540-24651-0_12, ISBN 978-3-540-21043-6, archivado (PDF) del original el 14 de marzo de 2016 , consultado el 17 de septiembre de 2011.
Garg, Ashim; Tamassia, Roberto (1995), "Prueba de planaridad ascendente", Order , 12 (2): 109–133, CiteSeerX 10.1.1.10.2237 , doi :10.1007/BF01108622, MR 1354797, S2CID 14183717.
Grandjean, Martin (2014), "La connaissance est un réseau", Les Cahiers du Numérique , 10 (3): 37–54, doi :10.3166/lcn.10.3.37-54, archivado desde el original el 2015-06- 27 , consultado el 15 de octubre de 2014..
Holten, Danny; Isenberg, Petra ; van Wijk, Jarke J.; Fekete, Jean-Daniel (2011), "Una evaluación extendida de la legibilidad de representaciones de bordes dirigidos texturizados, animados y cónicos en gráficos de nodos-enlaces", Simposio de visualización IEEE Pacific (PacificVis 2011) (PDF) , págs. 195–202, doi :10.1109/PACIFICVIS.2011.5742390, ISBN 978-1-61284-935-5, S2CID 16526781, archivado (PDF) del original el 2016-04-11 , recuperado el 2011-09-29.
Holten, Danny; van Wijk, Jarke J. (2009), "Un estudio de usuario sobre la visualización de bordes dirigidos en gráficos", Actas de la 27.ª Conferencia internacional sobre factores humanos en sistemas informáticos (CHI '09) (PDF) , pp. 2299–2308, CiteSeerX 10.1.1.212.5461 , doi :10.1145/1518701.1519054, ISBN 9781605582467, S2CID 9725345, archivado desde el original (PDF) el 6 de noviembre de 2011.
Knuth, Donald E. (2013), "Dos mil años de combinatoria", en Wilson, Robin; Watkins, John J. (eds.), Combinatorics: Ancient and Modern , Oxford University Press, págs. 7–37.
Koren, Yehuda (2005), "Dibujo de gráficos por vectores propios: teoría y práctica", Computers & Mathematics with Applications , 49 (11–12): 1867–1888, doi : 10.1016/j.camwa.2004.08.015 , MR 2154691.
Longabaugh, William (2012), "Peinando la bola de pelo con BioFabric: un nuevo enfoque para la visualización de redes grandes", BMC Bioinformatics , 13 : 275, doi : 10.1186/1471-2105-13-275 , PMC 3574047 , PMID 23102059.
Misue, K.; Eades, P.; Lai, W.; Sugiyama, K. (1995), "Ajuste de diseño y mapa mental", Journal of Visual Languages & Computing , 6 (2): 183–210, doi :10.1006/jvlc.1995.1010.
Pach, János ; Sharir, Micha (2009), "5.5 Resolución angular y pendientes", Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures , Mathematical Surveys and Monographs, vol. 152, American Mathematical Society , págs. 126–127.
Purchase, HC ; Cohen, RF; James, MI (1997), "Un estudio experimental de la base de los algoritmos de dibujo de gráficos", Journal of Experimental Algorithmics , 2 , artículo 4, doi :10.1145/264216.264222, S2CID 22076200.
Saaty, Thomas L. (1964), "El número mínimo de intersecciones en grafos completos", Proc. Natl. Acad. Sci. USA , 52 (3): 688–690, Bibcode : 1964PNAS...52..688S , doi : 10.1073/pnas.52.3.688 , PMC 300329 , PMID 16591215.
Scott, John (2000), "Sociogramas y teoría de grafos", Análisis de redes sociales: un manual (2.ª ed.), Sage, págs. 64-69, ISBN 978-0-7619-6339-4.
Zapponi, Leonardo (agosto de 2003), "What is a Dessin d'Enfant" (PDF) , Notices of the American Mathematical Society , 50 : 788–789, archivado (PDF) del original el 2021-10-03 , consultado el 2021-04-28.
Tamassia, Roberto , ed. (2014), Handbook of Graph Drawing and Visualization, CRC Press, archivado desde el original el 15 de agosto de 2013 , consultado el 28 de agosto de 2013.
Enlaces externos
Biblioteca GraphX para .NET Archivado el 26 de enero de 2018 en Wayback Machine : biblioteca WPF de código abierto para cálculo y visualización de gráficos. Admite muchos algoritmos de diseño y enrutamiento de bordes.
Archivo de impresiones electrónicas de dibujo gráfico: incluye información sobre los artículos de todos los simposios de dibujo gráfico .
Dibujo de gráficos en Curlie para muchos enlaces adicionales relacionados con el dibujo de gráficos.
