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. En el concreto, sin embargo, 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 bordes (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 gráficos se dibujan con frecuencia como diagramas de vínculos de nodos en los que los vértices se representan como discos, cuadros o etiquetas textuales y los bordes se representan como segmentos de línea , polilíneas o curvas en el plano euclidiano . [3] Los diagramas nodo-enlace se remontan a las obras de Pseudo-Lull de los siglos XIV-XVI que se publicaron bajo el nombre de Ramon Llull , un erudito del siglo XIII. Pseudo-Lull dibujó diagramas de este tipo para gráficos completos con el fin de analizar todas las combinaciones por pares entre conjuntos de conceptos metafísicos. [5]
En el caso de 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 la reducción gradual, proporcionan esta información de manera más efectiva. [6] El dibujo plano hacia arriba utiliza la convención de que cada borde está orientado desde un vértice inferior a un vértice superior, lo que hace innecesarias las puntas de flecha. [7]
Las convenciones alternativas a los diagramas de enlace de nodo incluyen representaciones de adyacencia, como empaquetamientos circulares , en las 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 separados 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 matemáticas de tren ; tejidos, en los que los nudos 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 gráficos, en un intento de encontrar medios objetivos para evaluar su estética y usabilidad. [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 cruce de un dibujo es el número de pares de aristas que se cruzan. Si el gráfico es plano , a menudo es conveniente dibujarlo sin intersecciones de bordes; 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 bordes. [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 cualesquiera. Los dibujos con áreas más pequeñas son generalmente preferibles a aquellos con áreas más grandes, porque permiten que las características del dibujo se muestren en mayor tamaño 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ía es el problema de encontrar grupos de simetría dentro de un gráfico determinado y encontrar un dibujo que muestre la mayor simetría posible. Algunos métodos de diseño conducen automáticamente a dibujos simétricos; Alternativamente, algunos métodos de dibujo comienzan encontrando simetrías en el gráfico de entrada y usándolas para construir un dibujo. [11]
Es importante que los bordes tengan formas lo más simples posible, para que la vista pueda seguirlos más fácilmente. En los dibujos de polilíneas, la complejidad de un borde se puede medir por su número de dobleces , y muchos métodos apuntan a proporcionar dibujos con pocos dobleces totales o pocos dobleces 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 comúnmente utilizadas se refieren a la longitud de los bordes: generalmente 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 un dibujo 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 estar limitada por una función del grado. [12]
El número de pendiente de un gráfico es el número mínimo de pendientes de borde distintas necesarias en un dibujo con bordes de segmentos de línea recta (que permiten cruces). Las gráficas cúbicas tienen un número de pendiente como máximo cuatro, pero las gráficas de grado cinco pueden tener un número de pendiente ilimitado; permanece abierto si el número de pendiente de los gráficos de grado 4 está acotado. [12]
Métodos de diseño
Una visualización de red basada en la fuerza. [13]
Existen muchas estrategias diferentes de diseño de gráficos:
En los sistemas de diseño basados en fuerzas , el software de dibujo de gráficos modifica la ubicación inicial de los vértices 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 . Normalmente, estos sistemas combinan fuerzas de atracción entre vértices adyacentes con fuerzas de repulsión 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 de una función de energía basada en el descenso de gradiente , 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 se diseñaron originalmente para problemas de diseño de VLSI y PCB , pero también se han adaptado para el dibujo de gráficos. Por lo general, implican un enfoque de múltiples fases en el que se planifica 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 orientaciones de los bordes para minimizar las curvaturas, los vértices se colocan de manera consistente con estas orientaciones y, finalmente, se diseña un diseño. La etapa de compactación reduce el área del dibujo. [dieciséis]
Los algoritmos de diseño de árboles muestran una formación similar a un árbol con raíces , adecuada para árboles . A menudo, en una técnica llamada "diseño de globo", los hijos de cada nodo del árbol se dibujan en un círculo que rodea el nodo, y los radios de estos círculos disminuyen en los niveles inferiores del árbol para que estos círculos no se superpongan. [17]
Los métodos de dibujo de gráficos en capas (a menudo llamados dibujo de estilo Sugiyama) son más adecuados para gráficos acíclicos dirigidos o gráficos que son casi acíclicos, como los gráficos de dependencias entre módulos o funciones en un sistema de software. En estos métodos, los nodos del gráfico se organizan en capas horizontales utilizando métodos como el algoritmo de 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 para minimizar los cruces. [18]
diagrama de arco
Los diagramas de arco , un estilo de diseño que data de la década de 1960, [19] colocan los vértices en una línea; Los bordes se pueden dibujar como semicírculos encima o 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 uno del otro. 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 varios 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 sólo si es accesible desde el otro vértice. De esta manera, el estilo de diseño hace que la relación de accesibilidad del gráfico sea visualmente evidente. [21]
Dibujos 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 ubicació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 codiciosa en la computación distribuida , y la literatura sobre 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 arista.
^ Di Battista y col. (1994), págs. vii-viii; Herman, Melançon & Marshall (2000), Sección 1.1, "Áreas de aplicación típicas".
^ ab Di Battista y col. (1994), pág. 6.
^ ab Di Battista y col. (1994), pág. viii.
^ Misue y col. (1995)
^ Knuth, Donald E. (2013), "Dos mil años de combinatoria", en Wilson, Robin; Watkins, John J. (eds.), Combinatoria: antigua y moderna , Oxford University Press, págs. 7–37.
^ Holten y van Wijk (2009); Holten et al. (2011).
^ Garg y Tamassia (1995).
^ Longabaugh (2012).
^ Di Battista y col. (1994), Sección 2.1.2, Estética, págs. 14-16; Compra, Cohen y James (1997).
^ Di Battista y col. (1994), pág.14.
^ Di Battista y col. (1994), pág. dieciséis.
^ ab Pach y Sharir (2009).
^ Publicado en Grandjean, Martín (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 27 de junio de 2015 . Consultado el 15 de octubre de 2014 .
^ Di Battista y col. (1994), Sección 2.7, "El enfoque dirigido por la fuerza", págs. 29 y 30, y Capítulo 10, "Métodos dirigidos por la fuerza", págs.
^ Beckman (1994); Koren (2005).
^ Di Battista y col. (1994), Capítulo 5, "Flujo y dibujos ortogonales", págs. 137-170; (Eiglsperger, Fekete y Klau 2001).
^ Sugiyama, Tagawa y Toda (1981); Bastert y Matuszewski (2001); Di Battista et al. (1994), Capítulo 9, "Dibujos en capas de dígrafos", págs.
^ Saaty (1964).
^ Doğrusöz, Madden y Madden (1997).
^ Di Battista y col. (1994), Sección 4.7, "Planos de dominancia", págs.
^ Scott (2000); Brandes, Freeman y Wagner (2014).
^ Di Battista y col. (1994), págs. 15-16, y Capítulo 6, "Flujo y planaridad ascendente", págs. 171-214; Freese (2004).
^ Zapponi (2003).
^ Anderson y cabeza (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).
^ GraphPlot Archivado el 3 de febrero de 2014 en la documentación de Wayback Machine Mathematica
^ "Tutorial de dibujo de gráficos". Archivado desde el original el 12 de septiembre de 2013 . Consultado el 27 de septiembre de 2012 .
^ Nachmanson, Robertson y Lee (2008).
^ "Tulip: un marco de visualización de gráficos enorme", 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); consulte también la presentación anterior de GD 2012 Archivada el 27 de mayo de 2016 en Wayback Machine.
Referencias
Di Battista, Giuseppe; Eades, Pedro ; Tamasia, Roberto ; Tollis, Ioannis G. (1994), "Algoritmos para dibujar gráficos: una bibliografía comentada", Geometría computacional: teoría y aplicaciones , 4 (5): 235–282, doi : 10.1016/0925-7721(94)00014-x , Archivado desde el original el 27 de marzo de 2016 , consultado el 19 de marzo de 2007..
Herman, Iván; Melançon, Guy; Marshall, M. Scott (2000), "Visualización de gráficos y navegación en visualización de información: una encuesta", IEEE Transactions on Visualization and Computer Graphics , 6 (1): 24–43, doi :10.1109/2945.841119.
Tamassia, Roberto , ed. (2014), Manual de visualización y dibujo de gráficos, CRC Press, archivado desde el original el 15 de agosto de 2013 , consultado el 28 de agosto de 2013..
Subtemas especializados
Anderson, James Andrés; 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, cristiano; Brandes, Ulrik ; Schreiber, Falk (2014), "Biological Networks", en Tamassia, Roberto (ed.), Manual de visualización y dibujo de gráficos , CRC Press, págs..
Bastardo, Oliver; Matuszewski, Christian (2001), "Dibujos en capas de dígrafos", en Kaufmann, Michael; Wagner, Dorothea (eds.), Dibujo de gráficos: métodos y modelos , Apuntes de conferencias sobre informática, 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 del gráfico espectral, Tech. Informe 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 gráfico ortogonal", en Kaufmann, Michael; Wagner, Dorothea (eds.), Dibujo de gráficos , Apuntes de conferencias sobre informática, vol. 2025, Springer Berlín / 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 ) ) , Apuntes de conferencias sobre informática, 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) desde el original el 14 de marzo de 2016 , consultado el 17 de septiembre de 2011.
Garg, Ashim; Tamassia, Roberto (1995), "Prueba de planaridad ascendente", Orden , 12 (2): 109–133, CiteSeerX 10.1.1.10.2237 , doi :10.1007/BF01108622, MR 1354797, S2CID 14183717.
Holten, Danny; Isenberg, Petra ; van Wijk, Jarke J .; Fekete, Jean-Daniel (2011), "Una evaluación ampliada de la legibilidad de representaciones de borde dirigido cónicas, animadas y texturizadas en gráficos de enlace de nodos", Simposio de visualización del Pacífico IEEE (PacificVis 2011) (PDF), págs . 202, doi :10.1109/PACIFICVIS.2011.5742390, ISBN 978-1-61284-935-5, S2CID 16526781, archivado (PDF) desde el original el 11 de abril de 2016 , consultado el 29 de septiembre de 2011.
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) , págs. 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.
Koren, Yehuda (2005), "Dibujo de gráficos mediante vectores propios: teoría y práctica", Computadoras y matemáticas con aplicaciones , 49 (11–12): 1867–1888, doi : 10.1016/j.camwa.2004.08.015 , SEÑOR 2154691.
Longabaugh, William (2012), "Peinar la bola de pelo con BioFabric: un nuevo enfoque para la visualización de grandes redes", 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", Geometría combinatoria y sus aplicaciones algorítmicas: las conferencias de Alcalá , estudios y monografías matemáticas, vol. 152, Sociedad Estadounidense de Matemáticas , págs. 126-127.
Compra, HC ; Cohen, RF; James, MI (1997), "Un estudio experimental de las bases de los algoritmos de dibujo de gráficos" (PDF) , Journal of Experimental Algorithmics , 2 , artículo 4, doi :10.1145/264216.264222, S2CID 22076200[ enlace muerto permanente ] .
Saaty, Thomas L. (1964), "El número mínimo de intersecciones en gráficos completos", Proc. Nacional. Acad. Ciencia. EE. UU. , 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) desde el original el 3 de octubre de 2021 , recuperado en 2021 -04-28.
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 impresión electrónica de dibujo gráfico: incluye información sobre artículos de todos los simposios de dibujo gráfico .
Dibujo de gráficos en Curlie para obtener muchos enlaces adicionales relacionados con el dibujo de gráficos.
