Dibujo de grafos

El dibujo de grafos es un área de las matemáticas y la informática que combina métodos de la teoría de gráficos geométricos y la visualización de información para obtener representaciones bidimensionales de gráficos que surgen de aplicaciones como el análisis de redes sociales, la cartografía, la lingüística y la bioinformática.

Un dibujo de un gráfico o diagrama de red es una representación pictórica de los vértices y bordes de un gráfico. Este dibujo no debe confundirse con el propio gráfico: a un mismo gráfico pueden corresponder diseños muy diferentes. En abstracto, todo lo 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 bordes dentro de un dibujo afecta su comprensibilidad, usabilidad, costo de fabricación y estética. El problema empeora si el gráfico cambia con el tiempo al agregar y eliminar bordes (dibujo dinámico del gráfico) y el objetivo es preservar el mapa mental del usuario.

Convenciones gráficas

Los gráficos 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 de línea, polilíneas o curvas en el plano euclidiano. Los diagramas de nodo-enlace se remontan a las obras de 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 gráficos completos con el fin de analizar todas las combinaciones por pares entre conjuntos de conceptos metafísicos.

En el caso de gráficos dirigidos, las puntas de flecha forman una convención gráfica de uso común para mostrar su orientación; sin embargo, los estudios de usuarios han demostrado que otras convenciones, como la reducción gradual, brindan esta información de manera más efectiva. 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.

Las convenciones alternativas a los diagramas de nodo-vínculo incluyen representaciones de adyacencia como empaques 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 intersecciones 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 obstrucciones entre sí; dibujos confluentes, en los que los bordes se representan como curvas suaves dentro de las vías del tren matemático; tejidos, en los que los nudos se representan como líneas horizontales y los bordes como líneas verticales; 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. 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 entre sí. 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.
• 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 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. 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 dado y encontrar un dibujo que muestre la mayor cantidad de 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 gráfico de entrada y usarlas para construir un dibujo.
• Es importante que los bordes tengan formas lo más simples posibles, para que sea más fácil para el ojo seguirlos. En los dibujos de polilínea, la complejidad de un borde se puede medir por su número de pliegues, y muchos métodos apuntan a proporcionar dibujos con pocos pliegues totales o pocos pliegues por borde. De manera similar, para las curvas spline, la complejidad de un borde puede medirse por el número de puntos de control en el borde.
• Varias medidas de calidad comúnmente utilizadas se refieren a las longitudes 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 el dibujo de un gráfico. Si un gráfico tiene vértices de alto grado, necesariamente tendrá una resolución angular pequeña, pero la resolución angular puede estar limitada por una función del grado.
• 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 segmento de línea recta (permitiendo cruces). Los gráficos cúbicos tienen un número de pendiente como máximo cuatro, pero los gráficos 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.

Métodos de diseño

Hay 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. 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 y 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.
• Los métodos de disposición espectral utilizan como coordenadas los vectores propios de una matriz como la laplaciana derivada de la matriz de adyacencia del gráfico.
• 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 PCB y VLSI, pero también se han adaptado para dibujar gráficos. Por lo general, implican un enfoque multifase en el que un gráfico de entrada se planariza 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, 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.
• Los algoritmos de diseño de árboles muestran una formación similar a un árbol enraizado, adecuada para los á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 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.
• Los métodos de dibujo de gráficos en capas (a menudo llamados dibujos 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.

• Los diagramas de arco, un estilo de diseño que data de la década de 1960, 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í desde varios 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.
• El dibujo de dominancia coloca los vértices de tal manera que un vértice está hacia arriba, hacia la derecha o ambos 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 gráfico sea visualmente evidente.

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

• Sociogramas, dibujos de una red social, como suelen ofrecer los software de análisis de redes sociales
• Diagramas de Hasse, un tipo de dibujo gráfico especializado en órdenes parciales.
• Dessin d'enfants, un tipo de dibujo gráfico utilizado en geometría algebraica
• Diagramas de estado, representaciones gráficas de máquinas de estado finito
• Diagramas de redes informáticas, representaciones de los nodos y conexiones en una red informática
• Diagramas de flujo y diagramas de drakon, dibujos en los que los nodos representan los pasos de un algoritmo y los bordes representan el flujo de control entre pasos.
• Diagramas de flujo de datos, dibujos en los que los nodos representan los componentes de un sistema de información y los bordes representan el movimiento de información de un componente a otro.
• Bioinformática, incluidos árboles filogenéticos, redes de interacción proteína-proteína y vías metabólicas.

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 de dibujo de gráficos 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 gráficos generalmente solo involucra pares de vértices para cada borde.

Software

El software, los sistemas y los proveedores de sistemas para dibujar gráficos incluyen:

• Software de código abierto BioFabric para visualizar grandes redes dibujando nodos como líneas horizontales.
• Cytoscape, software 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 gratuita de Python para el análisis de gráficos.
• Graphviz, un sistema de dibujo de gráficos de código abierto de AT&T Corporation
• Linkurious, un software comercial de análisis y visualización de redes para bases de datos de gráficos
• Mathematica, una herramienta de computación de propósito general que incluye visualización de gráficos 2D y 3D y herramientas de análisis de gráficos.
• Microsoft Automatic Graph Layout, biblioteca.NET de código abierto (anteriormente llamada GLEE) para diseñar gráficos
• NetworkX es una biblioteca de Python para estudiar gráficos y redes.
• Tulip (software), 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
• PGF/TikZ 3.0 con el graphdrawingpaquete (requiere LuaTeX).
• LaNet-vi, un software de visualización de redes grandes de código abierto
• Edraw Max software de diagramación técnica empresarial 2D