Dibujo de gráficos

El dibujo de grafos es un área de las matemáticas y la informática que combina métodos de la teoría geométrica de grafos y la visualización de información para derivar representaciones bidimensionales (o, a veces, tridimensionales) de grafos que surgen de aplicaciones como el análisis de redes sociales , la cartografía , la lingüística y la bioinformática . ^{[ 1 ]}

Un dibujo de un grafo o diagrama de red es una representación gráfica de los vértices y aristas de un grafo. Este dibujo no debe confundirse con el grafo en sí: diseños muy diferentes pueden corresponder al mismo grafo. ^{[ 2 ]} En abstracto, lo único que importa es qué pares de vértices están conectados por aristas. En concreto, sin embargo, la disposición de estos vértices y aristas dentro de un dibujo afecta su comprensibilidad, usabilidad, coste de fabricación y estética . ^{[ 3 ]} El problema se agrava si el grafo cambia con el tiempo mediante la adición y eliminación de aristas (dibujo dinámico de grafos) y el objetivo es preservar el mapa mental del usuario. ^{[ 4 ]}

Los grafos se suelen representar como diagramas de nodos y enlaces, donde los vértices se representan como discos, cajas o etiquetas textuales, y las aristas como segmentos de línea , polilíneas o curvas en el plano euclidiano . ^{[ 3 ]} Los diagramas de nodos y enlaces se remontan a las obras de Pseudo-Lull de los siglos XIV al XVI, publicadas 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 posibles entre conjuntos de conceptos metafísicos. ^{[ 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.
• Symmetry display is the problem of finding symmetry groups within a given graph, and finding a drawing that displays as much of the symmetry as possible. Some layout methods automatically lead to symmetric drawings; alternatively, some drawing methods start by finding symmetries in the input graph and using them to construct a drawing.^[11]
• It is important that edges have shapes that are as simple as possible, to make it easier for the eye to follow them. In polyline drawings, the complexity of an edge may be measured by its number of bends, and many methods aim to provide drawings with few total bends or few bends per edge. Similarly for spline curves the complexity of an edge may be measured by the number of control points on the edge.
• Several commonly used quality measures concern lengths of edges: it is generally desirable to minimize the total length of the edges as well as the maximum length of any edge. Additionally, it may be preferable for the lengths of edges to be uniform rather than highly varied.
• Angular resolution is a measure of the sharpest angles in a graph drawing. If a graph has vertices with high degree then it necessarily will have small angular resolution, but the angular resolution can be bounded below by a function of the degree.^[12]
• The slope number of a graph is the minimum number of distinct edge slopes needed in a drawing with straight line segment edges (allowing crossings). Cubic graphs have slope number at most four, but graphs of degree five may have unbounded slope number; it remains open whether the slope number of degree-4 graphs is bounded.^[12]

There are many different graph layout strategies:

• In force-based layout systems, the graph drawing software modifies an initial vertex placement by continuously moving the vertices according to a system of forces based on physical metaphors related to systems of springs or molecular mechanics. Typically, these systems combine attractive forces between adjacent vertices with repulsive forces between all pairs of vertices, in order to seek a layout in which edge lengths are small while vertices are well-separated. These systems may perform gradient descent based minimization of an energy function, or they may translate the forces directly into velocities or accelerations for the moving vertices.^[14]
• Spectral layout methods use as coordinates the eigenvectors of a matrix such as the Laplacian derived from the adjacency matrix of the graph.^[15]
• Orthogonal layout methods, which allow the edges of the graph to run horizontally or vertically, parallel to the coordinate axes of the layout. These methods were originally designed for VLSI and PCB layout problems but they have also been adapted for graph drawing. They typically involve a multiphase approach in which an input graph is planarized by replacing crossing points by vertices, a topological embedding of the planarized graph is found, edge orientations are chosen to minimize bends, vertices are placed consistently with these orientations, and finally a layout compaction stage reduces the area of the drawing.^[16]
• Tree layout algorithms these show a rooted tree-like formation, suitable for trees. Often, in a technique called "balloon layout", the children of each node in the tree are drawn on a circle surrounding the node, with the radii of these circles diminishing at lower levels in the tree so that these circles do not overlap.^[17]
• Layered graph drawing methods (often called Sugiyama-style drawing) are best suited for directed acyclic graphs or graphs that are nearly acyclic, such as the graphs of dependencies between modules or functions in a software system. In these methods, the nodes of the graph are arranged into horizontal layers using methods such as the Coffman–Graham algorithm, in such a way that most edges go downwards from one layer to the next; after this step, the nodes within each layer are arranged in order to minimize crossings.^[18]

• Arc diagrams, a layout style dating back to the 1960s,^[19] place vertices on a line; edges may be drawn as semicircles above or below the line, or as smooth curves linked together from multiple semicircles.
• Circular layout methods place the vertices of the graph on a circle, choosing carefully the ordering of the vertices around the circle to reduce crossings and place adjacent vertices close to each other. Edges may be drawn either as chords of the circle or as arcs inside or outside of the circle. In some cases, multiple circles may be used.^[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 .