Dibujo de grafos

De Wikipedia, la enciclopedia libre
Este artículo trata sobre el tema general del dibujo de grafos. Para el simposio anual de investigación, véase International Symposium on Graph Drawing.
Representación gráfica de una fracción de minuto de la World Wide Web, mostrando sus hiperenlaces

El dibujo de grafos es un área de las matemáticas y de las ciencias de la computación que combina métodos de la teoría de grafos geométrica y de visualización de datos para obtener representaciones bidimensionales de grafos que surgen de aplicaciones como el análisis de redes sociales, la cartografía, la lingüística o la bioinformática.[1]​

Un dibujo de un grafo o diagrama de red es una representación pictórica de los vértices y de las conexiones de un grafo. Este dibujo no debe confundirse con el propio grafo: a un mismo grafo pueden corresponder diseños muy diferentes.[2]​ En abstracto, todo lo que importa es qué pares de vértices están conectados por las aristas. En 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 grafo cambia con el tiempo agregando y eliminando bordes (dibujo dinámico del grafo) y el objetivo es preservar el mapa mental del usuario.[4]​

Convenciones gráficas[editar]

Grafo dirigido con puntas de flecha indicando las direcciones de flujo

Los grafos se dibujan con frecuencia como diagramas de nodo-vínculo en los que los vértices se representan como discos, cajas o etiquetas de texto y los bordes se representan como segmentos, polilíneas o curvas sobre un medio bidimensional. Los diagramas de enlace de nodos[3]​ se remontan a las obras del Pseudo-Lull de los siglos XIV-XVI que se publicaron con el nombre de Ramon Llull, un erudito del siglo XIII. Pseudo-Lull dibujó diagramas de este tipo para obtener un grafo completo con el fin de analizar todas las combinaciones por pares entre conjuntos de conceptos metafísicos.[5]​

En el caso de los grafos dirigidos, se utilizan flechas que forman una convención gráfica de uso común para mostrar su orientación.[2]​ Sin embargo, los estudios de usuarios han demostrado que otras convenciones, como la reducción gradual del tamaño de los nodos brindan esta información de manera más efectiva.[6]​ En un dibujo plano hacia arriba se usa la convención de que cada vínculo 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 nodo-enlace incluyen representaciones de adyacencia como el empaquetado de círculos, 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 disjuntos y los vínculos 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 vínculos están representados por regiones que tienen una línea de visión sin obstrucciones entre sí; dibujos confluentes, en los que los vínculos 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 vínculos como líneas verticales;[8]​ y visualizaciones de la matriz de adyacencia del grafo.

Medidas de calidad[editar]

Se han definido muchas medidas de calidad diferentes para los dibujos grafos, 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 grafo, algunos métodos de diseño intentan optimizar directamente estas medidas.

Grafo plano dibujado sin vínculos superpuestos
  • El número de cruce de un dibujo es el número de pares de vínculos que se cruzan entre sí. Si el grafo es plano, a menudo es conveniente dibujarlo sin intersecciones de vínculos; es decir, en este caso, el dibujo de un grafo representa un grafo embebido. Sin embargo, los grafos no planos surgen con frecuencia en las aplicaciones, por lo que los algoritmos de dibujo de grafos generalmente deben permitir cruces de vínculos.[10]​
  • El área de un dibujo es el tamaño de su cuadro delimitador más pequeño, en relación con la menor distancia entre dos vértices cualesquiera. Los dibujos con un área más pequeña son generalmente preferibles a aquellos con un área más grande, porque permiten que las características del dibujo se muestren en mayor tamaño y, por lo tanto, de manera más legible. El proporción del cuadro delimitador también puede ser importante.
  • La visualización de simetría es el problema de hallar un grupo de simetría dentro de un grafo dado 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 por encontrar simetrías en el grafo de entrada para usarlas en la construcción del dibujo.[11]​
  • Es importante que los vínculos tengan formas lo más simples posibles, para que sea más fácil para el ojo seguirlos. En los dibujos con polilíneas, la complejidad de un vínculo se puede medir por su número de recodos, y muchos métodos apuntan a proporcionar dibujos con pocos quiebros totales o pocos recodos por vínculo. De manera similar, para las curvas suavizadas, la complejidad de un vínculo puede medirse por el número de puntos de control que requieren.
  • Varias medidas de calidad comúnmente utilizadas se refieren a la longitud de los vínculos: generalmente es deseable minimizar su longitud total, así como la longitud máxima de cualquiera de ellos. Además, puede ser preferible que sus longitudes 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 grafo. Si un grafo tiene vértices de grado alto, 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 pendientes de un grafo es el número mínimo de pendientes de un vínculo distintas necesarias en un dibujo con vínculos de segmento de línea recta (permitiendo cruces). Los grafos cúbicos tienen un número de pendientes por lo general cuatro, pero los grafos de grado cinco pueden tener un número de pendientes ilimitado; y permanece abierto si el número de pendientes de los grafos de grado 4 está acotado.[12]​

Métodos de diseño[editar]

Una visualización de red basada en sistema de fuerzas.[13]​

Existen muchas estrategias de diseño de grafos diferentes:

  • En los métodos de diseño basado en la fuerza, los programas de dibujo de grafos modifican la ubicación inicial de un vértice moviendo continuamente los vértices según un sistema de fuerzas basado en metáforas físicas relacionadas con los sistemas de resortes o la 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 vínculos sean pequeñas y los vértices estén bien separados. Estos sistemas pueden realizar una minimización basada en una optimización del descenso de gradiente, o pueden traducir las fuerzas directamente en velocidades o aceleraciones para los vértices en movimiento.[14]​
  • Los métodos de diseño espectral utilizan como coordenadas los autovectores de una matriz, como el operador laplaciano derivado de la matriz de adyacencia del grafo.[15]​
  • Métodos de diseño ortogonal, que permiten que los vínculos del grafo se extiendan horizontal o verticalmente, paralelos a los ejes de coordenadas del diseño. Estos métodos se idearon originalmente para resolver problemas de diseño de integración a muy gran escala y de circuitos impresos, pero también se han adaptado para dibujar grafos. Por lo general, implican un enfoque multifase en el que un grafo de entrada se planariza reemplazando los puntos de cruce por vértices, se encuentra un embebido topológico del grafo planarizado, se eligen las orientaciones de los vínculos para minimizar las curvas, los vértices se colocan de manera consistente con estas orientaciones y finalmente un diseño etapa de compactación reduce el área del dibujo.[16]​
  • Los algoritmos de diseño de árbol muestran una formación similar a árboles enraizados, adecuada para grafos en árbol. A menudo, en una técnica llamada diseño de globo, los hijos de cada nodo en el árbol se dibujan en un círculo que rodea el nodo, y los radios de estos círculos disminuyen en los niveles más bajos del árbol para que estos círculos no se superpongan.[17]​
  • Los métodos dibujo de grafos por capas (a menudo llamados dibujos de estilo Sugiyama) son 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 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 arcos
  • Diagramas de arcos, un estilo de diseño que data de la década de 1960,[19]​ en el que se colocan los vértices en una línea, y los vínculos se dibujan como semicírculos por encima o por debajo de la línea, o como curvas suaves unidas entre sí desde varios semicírculos.
  • Los métodos de diseño circular colocan los vértices del grafo 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 unos cerca uno de los otros. Los vínculos 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 método de dibujo de dominancia coloca los vértices de tal manera que un vértice está hacia arriba, hacia la derecha o de ambas formas si y solo si es accesible desde el otro vértice. De esta forma, el estilo de diseño hace que la relación de accesibilidad del grafo sea visualmente evidente.[21]​

Dibujos de grafos específicos según su aplicación[editar]

Los grafos y dibujos de grafos que surgen en otras áreas de aplicación incluyen:

Además, los pasos colocación y enrutamiento para la automatización de diseño electrónico (EDA) son similares en muchos aspectos al dibujo de grafos, al igual que el problema de embebido ávido en computación distribuida, y la literatura de dibujo de grafos incluye varios resultados tomados de la literatura de EDA. Sin embargo, estos problemas también difieren en varias formas 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 grafos generalmente solo involucra pares de vértices para cada vínculo.

Software[editar]

Una interfaz de dibujo de grafos (Gephi 0.9.1)

Programas, sistemas y proveedores de sistemas para dibujar grafos incluyen:

  • Software de código abierto BioFabric para visualizar grandes redes dibujando nodos como líneas horizontales.
  • Cytoscape, programa de código abierto para visualizar redes de interacción molecular.
  • Gephi, software de visualización y análisis de redes de código abierto.
  • graph-tool, una biblioteca libre en Python para el análisis de grafos.
  • Graphviz, un sistema de dibujo de grafos de código abierto de AT&T Corporation.[28]​
  • Linkurious, un análisis de red comercial y software de visualización para bases de datos orientadas a grafos.
  • Mathematica, una herramienta de computación de propósito general que incluye visualización de grafos en 2D y 3D y herramientas de análisis de grafos.[29]​[30]​
  • Microsoft Automatic Graph Layout, biblioteca .NET de código abierto (anteriormente llamada GLEE) para diseñar grafos.[31]​
  • NetworkX es una biblioteca de Python para estudiar grafos y redes.
  • Tulip (software),[32]​ una herramienta de visualización de datos de código abierto.
  • yEd, un editor de grafos con funcionalidades de diseño.[33]​
  • PGF/TikZ 3.0 con el paquete graphdrawing (requiere LuaTeX).[34]​
  • LaNet-vi, un software de código abierto de visualización de redes grandes.
  • Software de diagramación técnica comercial Edraw Max 2D.

Véase también[editar]

Referencias[editar]

  1. ↑ Di Battista et al. (1994), pp. vii–viii;Herman, Melançon y Marshall (2000), Section 1.1, "Typical Application Areas".
  2. ↑ a b Di Battista et al. (1994), p. 6.
  3. ↑ a b Di Battista et al. (1994), p. viii.
  4. ↑ Misue et al. (1995)
  5. ↑ Knuth, Donald E. (2013), «Two thousand years of combinatorics», en Wilson, Robin; Watkins, John J., eds., Combinatorics: Ancient and Modern, Oxford University Press, pp. 7-37 ..
  6. ↑ Holten y van Wijk (2009);Holten et al. (2011).
  7. ↑ Garg y Tamassia (1995).
  8. ↑ Longabaugh (2012).
  9. ↑ Di Battista et al. (1994), Section 2.1.2, Aesthetics, pp. 14–16;Purchase, Cohen y James (1997).
  10. ↑ Di Battista et al. (1994), p 14.
  11. ↑ Di Battista et al. (1994), p. 16.
  12. ↑ a b Pach y Sharir (2009).
  13. ↑ Published in 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. Consultado el 15 de octubre de 2014. 
  14. ↑ Di Battista et al. (1994), Section 2.7, "The Force-Directed Approach", pp. 29–30, and Chapter 10, "Force-Directed Methods", pp. 303–326.
  15. ↑ Beckman (1994);Koren (2005).
  16. ↑ Di Battista et al. (1994), Chapter 5, "Flow and Orthogonal Drawings", pp. 137–170;(Eiglsperger, Fekete y Klau, 2001).
  17. ↑ Herman, Melançon y Marshall (2000), Section 2.2, "Traditional Layout – An Overview".
  18. ↑ Sugiyama, Tagawa y Toda (1981);Bastert y Matuszewski (2001);Di Battista et al. (1994), Chapter 9, "Layered Drawings of Digraphs", pp. 265–302.
  19. ↑ Saaty (1964).
  20. ↑ Doğrusöz, Madden y Madden (1997).
  21. ↑ Di Battista et al. (1994), Section 4.7, "Dominance Drawings", pp. 112–127.
  22. ↑ Scott (2000);Brandes, Freeman y Wagner (2014).
  23. ↑ Di Battista et al. (1994), pp. 15–16, and Chapter 6, "Flow and Upward Planarity", pp. 171–214;Freese (2004).
  24. ↑ Zapponi, 2003.
  25. ↑ Anderson y Head, 2006.
  26. ↑ Di Battista y Rimondini, 2014.
  27. ↑ Bachmaier, Brandes y Schreiber, 2014.
  28. ↑ "Graphviz and Dynagraph – Static and Dynamic Graph Drawing Tools", by John Ellson, Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North, and Gordon Woodhull, in Jünger y Mutzel (2004).
  29. ↑ GraphPlot Mathematica documentation
  30. ↑ Graph drawing tutorial
  31. ↑ Nachmanson, Robertson y Lee (2008).
  32. ↑ "Tulip – A Huge Graph Visualization Framework", by David Auber, in Jünger y Mutzel (2004).
  33. ↑ "yFiles – Visualization and Automatic Layout of Graphs", by Roland Wiese, Markus Eiglsperger, and Michael Kaufmann, in Jünger y Mutzel (2004).
  34. ↑ Tantau (2013); véase también la antigua presentación GD 2012

Bibliografía[editar]

Subtemas especializados

Enlaces externos[editar]

Obtenido de «https://es.wikipedia.org/w/index.php?title=Dibujo_de_grafos&oldid=159576315»