Graph drawing

Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional (or, sometimes, three-dimensional) depictions of graphs arising from applications such as social network analysis, cartography, linguistics, and bioinformatics.^[1]

A drawing of a graph or network diagram is a pictorial representation of the vertices and edges of a graph. This drawing should not be confused with the graph itself: very different layouts can correspond to the same graph.^[2] In the abstract, all that matters is which pairs of vertices are connected by edges. In the concrete, however, the arrangement of these vertices and edges within a drawing affects its understandability, usability, fabrication cost, and aesthetics.^[3] The problem gets worse if the graph changes over time by adding and deleting edges (dynamic graph drawing) and the goal is to preserve the user's mental map.^[4]

Graphs are frequently drawn as node–link diagrams in which the vertices are represented as disks, boxes, or textual labels and the edges are represented as line segments, polylines, or curves in the Euclidean plane.^[3] Node–link diagrams can be traced back to the 14th-16th century works of Pseudo-Lull which were published under the name of Ramon Llull, a 13th century polymath. Pseudo-Lull drew diagrams of this type for complete graphs in order to analyze all pairwise combinations among sets of metaphysical concepts.^[5]

En el caso de los grafos dirigidos , las puntas de flecha constituyen una convención gráfica de uso común para mostrar su orientación ; ^{[ 2 ]} sin embargo, estudios de usuarios han demostrado que otras convenciones, como el ahusamiento, proporcionan esta información de manera más efectiva. ^{[ 6 ]} El dibujo planar ascendente utiliza la convención de que cada arista está orientada desde un vértice inferior a uno superior, lo que hace innecesarias las puntas de flecha. ^{[ 7 ]}

Las convenciones alternativas a los diagramas de nodos y enlaces incluyen representaciones de adyacencia como empaquetamientos de círculos , en los que los vértices se representan mediante regiones disjuntas en el plano y las aristas se representan mediante adyacencias entre regiones; representaciones de intersección en las que los vértices se representan mediante objetos geométricos no disjuntos y las aristas se representan mediante sus intersecciones; representaciones de visibilidad en las que los vértices se representan mediante regiones en el plano y las aristas se representan mediante regiones que tienen una línea de visión sin obstrucciones entre sí; dibujos confluentes, en los que las aristas 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 las aristas como líneas verticales; ^{[ 8 ]} y visualizaciones de la matriz de adyacencia del grafo.

Se han definido diversas medidas de calidad para los dibujos de gráficos, en un intento por 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 cruces de un dibujo es la cantidad de pares de aristas que se cruzan entre sí. Si el grafo es planar , suele ser conveniente dibujarlo sin intersecciones de aristas; es decir, en este caso, un dibujo de grafo representa una incrustación de grafo . Sin embargo, los grafos no planares aparecen con frecuencia en las aplicaciones, por lo que los algoritmos de dibujo de grafos 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 corta entre dos vértices cualesquiera. Los dibujos con un área menor suelen ser preferibles a los de área mayor, ya que permiten mostrar los detalles del dibujo a mayor tamaño y, por lo tanto, con mayor legibilidad. La relación de aspecto del cuadro delimitador también puede ser importante.
• La representación de simetría consiste en encontrar grupos de simetría dentro de un grafo dado y generar un dibujo que muestre la mayor cantidad posible de simetría. Algunos métodos de diseño generan automáticamente dibujos simétricos; otros, en cambio, comienzan por encontrar simetrías en el grafo de entrada y las utilizan para construir un dibujo. ^{[ 11 ]}
• Es importante que los bordes tengan formas lo más simples posible para facilitar su seguimiento visual. En los dibujos de polilíneas, la complejidad de un borde se puede medir por el número de curvas , y muchos métodos buscan generar dibujos con pocas curvas en total o pocas curvas por borde. De manera similar, en las curvas spline, la complejidad de un borde se puede medir por el número de puntos de control en el mismo.
• Varias medidas de calidad de uso común se refieren a la longitud de los bordes: generalmente se busca minimizar tanto la longitud total como la máxima de cada borde. Además, puede ser preferible que las longitudes de los bordes sean uniformes en lugar de muy variables.
• La resolución angular es una medida de los ángulos más agudos en un dibujo de grafo. Si un grafo tiene vértices con un grado alto , necesariamente tendrá una resolución angular pequeña, pero la resolución angular puede estar acotada inferiormente por una función del grado. ^{[ 12 ]}
• El número de pendiente de un grafo es el número mínimo de pendientes de arista distintas necesarias en un dibujo con aristas de segmento de línea recta (permitiendo cruces). Los grafos cúbicos tienen como máximo un número de pendiente de cuatro, pero los grafos de grado cinco pueden tener un número de pendiente ilimitado; sigue siendo una incógnita si el número de pendiente de los grafos de grado 4 está acotado. ^{[ 12 ]}

Existen muchas estrategias diferentes para el diseño de gráficos:

• En los sistemas de diseño basados ​​en fuerzas , el software de dibujo de grafos modifica la posición inicial de los vértices moviéndolos continuamente según un sistema de fuerzas basado en metáforas físicas relacionadas con sistemas de resortes o mecánica molecular . Normalmente, 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 las aristas sean pequeñas y los vértices estén bien separados. Estos sistemas pueden realizar una minimización de una función de energía mediante descenso de gradiente , o bien 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 laplaciano derivado de la matriz de adyacencia del grafo. ^{[ 15 ]}
• Métodos de diseño ortogonal, que permiten que las aristas del grafo se extiendan horizontal o verticalmente, paralelas a los ejes de coordenadas del diseño. Estos métodos fueron diseñados originalmente para problemas de diseño de VLSI y PCB , pero también se han adaptado para el dibujo de grafos. Generalmente implican un enfoque multifase en el que un grafo de entrada se planariza reemplazando los puntos de cruce por vértices, se encuentra una incrustación topológica del grafo planarizado, se eligen las orientaciones de las aristas para minimizar las curvas, los vértices se colocan de manera consistente con estas orientaciones y, finalmente, una etapa de compactación del diseño reduce el área del dibujo. ^{[ 16 ]}
• Los algoritmos de diseño de árboles muestran una formación similar a un árbol con raíz , adecuada para árboles . 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 al nodo, con radios de estos círculos que disminuyen en los niveles inferiores del árbol para que estos círculos no se superpongan. ^{[ 17 ]}
• Los métodos de dibujo de grafos por capas (a menudo denominados dibujo al estilo Sugiyama) son los más adecuados para grafos dirigidos acíclicos o grafos 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 manera que la mayoría de las aristas descienden de una capa a la siguiente; después de este paso, los nodos dentro de cada capa se organizan para minimizar los cruces. ^{[ 18 ]}

• 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 pueden dibujarse 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 disposición 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 cerca unos de otros. Las aristas pueden dibujarse como cuerdas del círculo o como arcos dentro o fuera del círculo. En algunos casos, pueden utilizarse varios círculos. ^{[ 20 ]}
• El dibujo de dominancia coloca los vértices de tal manera que un vértice se encuentra arriba, a la derecha o en ambas direcciones con respecto a otro si y solo si es alcanzable desde ese otro vértice. De esta forma, el estilo de diseño hace visualmente evidente la relación de alcanzabilidad del grafo. ^{[ 21 ]}

Los gráficos y los dibujos de gráficos que surgen en otras áreas de aplicación incluyen:

• Sociogramas , dibujos de una red social , como los que suelen ofrecer los programas de análisis de redes sociales ^{[ 22 ].}
• Diagramas de Hasse , un tipo de dibujo de gráficos especializado en órdenes parciales ^{[ 23 ]}
• Dessin d'enfants , un tipo de dibujo de gráficos utilizado en geometría algebraica ^{[ 24 ]}
• Diagramas de estados , representaciones gráficas de máquinas de estados finitos ^{[ 25 ]}
• Diagramas de redes informáticas , representaciones de los nodos y conexiones en una red informática ^{[ 26 ]}
• Diagramas de flujo y diagramas de Drakon , dibujos en los que los nodos representan los pasos de un algoritmo y las aristas representan el flujo de control entre los pasos.
• Red de proyecto , representación gráfica del orden cronológico en que deben completarse las actividades de un proyecto .
• Diagramas de flujo de datos , dibujos en los que los nodos representan los componentes de un sistema de información y las aristas representan el movimiento de información de un componente a otro.
• Bioinformática que incluye árboles filogenéticos , redes de interacción proteína-proteína y vías metabólicas . ^{[ 27 ]}

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 grafos, al igual que el problema de la incrustación voraz en la computación distribuida , y la literatura sobre dibujo de grafos incluye varios resultados tomados de la literatura sobre 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 grafos generalmente solo involucra pares de vértices para cada arista.

Existen muchos algoritmos para dibujar grafos. Entre ellos se encuentran:

• El algoritmo Reingold-Tilford para el dibujo de árboles. ^{[ 28 ]}
• El algoritmo de Kant, ^{[ 29 ]} que construye un dibujo de polilínea de un grafo planar 3-conexo de tal manera que el tamaño del ángulo mínimo entre arcos sea al menos${\displaystyle {\frac {1}{d}}\pi }$, donde d es el grado máximo del nodo; y su generalización, que también funciona bien para otros grafos planares, por Gutwenger y Mutzel. ^{[ 30 ]}
• Algoritmo de Tamassia para minimizar el número de curvaturas en una representación ortogonal de un grafo planar. ^{[ 31 ]}
• El modelo de resorte magnético de Sugiyama y Misue. ^{[ 32 ]}

Entre los programas, sistemas y proveedores de sistemas para dibujar gráficos se incluyen:

• BioFabric es un software de código abierto para visualizar grandes redes dibujando los nodos como líneas horizontales.
• Cytoscape , software de código abierto para visualizar redes de interacción molecular.
• Gephi , software de análisis y visualización de redes de código abierto
• graph-tool , una biblioteca Python gratuita para el análisis de gráficos.
• Graphviz , un sistema de dibujo de gráficos de código abierto de AT&T Corporation ^{[ 33 ]}
• Linkurious , un software comercial de análisis y visualización de redes para bases de datos de grafos.
• Mathematica , una herramienta de cálculo de propósito general que incluye herramientas de visualización y análisis de gráficos en 2D y 3D. ^{[ 34 ]}
• Microsoft Automatic Graph Layout , biblioteca .NET de código abierto (anteriormente llamada GLEE) para diseñar gráficos ^{[ 35 ]}
• NetworkX es una biblioteca de Python para el estudio de grafos y redes.
• Tulip , ^{[ 36 ]} una herramienta de visualización de datos de código abierto
• yEd , un editor de gráficos con funcionalidad de diseño de gráficos ^{[ 37 ]}
• PGF/TikZ 3.0 con el graphdrawingpaquete (requiere LuaTeX ). ^{[ 38 ]}
• LaNet-vi , un software de visualización de redes grandes de código abierto
• OGDF, una biblioteca de código abierto de estructuras de datos y algoritmos de C++, principalmente para el dibujo de gráficos ^{[ 39 ]}

• Simposio Internacional sobre Dibujo Gráfico
• Lista de herramientas del Lenguaje Unificado de Modelado

• Biblioteca GraphX ​​para .NET (archivada el 26/01/2018 en Wayback Machine) : biblioteca WPF de código abierto para el cálculo y la visualización de gráficos. Admite numerosos algoritmos de diseño y enrutamiento de aristas.
• Archivo electrónico de preimpresiones sobre dibujo gráfico : incluye información sobre artículos de todos los simposios sobre dibujo gráfico .