Dibujo gráfico

Drawing de gráficos es un área de matemáticas y ciencias de la computación que combina métodos de la teoría geométrica de gráficos y la visualización de la 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,, la lingüística, y bioinformática.

Un dibujo de un gráfico o el 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 gráfico en sí: los diseños muy diferentes pueden corresponder al mismo gráfico. En abstracto, todo lo que importa es qué pares de vértices están conectados por bordes. Sin embargo, en el concreto, la disposición de estos vértices y bordes dentro de un dibujo afecta su comprensión, usabilidad, costo de fabricación y estética. El problema empeora si el gráfico cambia con el tiempo al agregar y eliminar los bordes (dibujo de gráficos dinámicos) y el objetivo es preservar el mapa mental del usuario.

Convenciones gráficas

se dibujan con frecuencia como diagramas de nodo -enlace 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. Los diagramas de nodo-enlace se remontan a las obras del siglo XIV al XVI de pseudo-lull que se publicaron bajo el nombre de Ramon Llull, un polímato del siglo XIII. Los diagramas de pseudo-lubricación dibujaron este tipo para gráficos completos para analizar todas las combinaciones por pares entre conjuntos de conceptos metafísicos.

En el caso de los gráficos dirigidos, las puntas de flecha forman una convención gráfica comúnmente utilizada para mostrar su orientación; Sin embargo, los estudios de usuarios han demostrado que otras convenciones, como la reducción, proporcionan 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 hasta un vértice más alto, lo que hace que las puntas de flecha sean innecesarias.

Las convenciones alternativas a los diagramas de nodo -enlace incluyen representaciones de adyacencia, como los empaquetados de círculo, 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; Las representaciones de intersección en las que los vértices están representados por objetos y bordes geométricos no desanimados están representadas por sus intersecciones; Las representaciones de visibilidad en las que los vértices están representados por regiones en el plano y los bordes están representadas 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 las vías del tren matemático; Las telas, en las que los nodos se representan como líneas horizontales y 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 de gráficos, en un intento por 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 bordes que se cruzan entre sí. Si el gráfico es plano, entonces es conveniente dibujarlo sin intersecciones de bordes; es decir, en este caso, un dibujo gráfico representa un embedding gráfico. Sin embargo, los gráficos no planas surgen con frecuencia en aplicaciones, por lo que los algoritmos de dibujo gráfico generalmente deben permitir cruces de bordes.
• El área de un dibujo es el tamaño de su caja más pequeña, relativa a la distancia más cercana entre cualquier dos vértices. Los dibujos con área más pequeña son generalmente preferibles a aquellos con área más grande, porque permiten que las características del dibujo se muestren en mayor tamaño y por lo tanto más legible. La relación de aspecto de la caja de fijación también puede ser importante.
• La pantalla 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 parte de la 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 utilizarlos para construir un dibujo.
• Es importante que los bordes tengan formas tan simples como sea posible, para facilitar que el ojo las siga. En los dibujos de polilínea, la complejidad de un borde se puede medir por su número de curvas, y muchos métodos tienen como objetivo proporcionar dibujos con pocas curvas totales o pocas curvas por borde. Del mismo modo para las curvas de estilización la complejidad de un borde se puede medir por el número de puntos de control en el borde.
• Varias medidas de calidad utilizadas se refieren a longitudes de 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 alto grado, entonces necesariamente tendrá pequeña resolución angular, pero la resolución angular puede ser atada abajo por una función del grado.
• El número de pendiente de un gráfico es el número mínimo de pendientes de bordes distintos que se necesitan en un dibujo con bordes de segmento de línea recta (pasos adyacentes). Los gráficos cúbicos tienen la pendiente número a la mayoría de cuatro, pero los gráficos del grado cinco pueden tener un número de pendiente sin límites; permanece abierto si el número de pendiente de los gráficos de grado-4 está ligado.

Métodos de diseño

Hay muchas estrategias de diseño de gráficos diferentes:

• En sistemas de diseño basados en la fuerza, el software de dibujo gráfico modifica una colocación inicial del vértice moviendo continuamente los vértices según un sistema de fuerzas basado en metáforas físicas relacionadas con sistemas de muelles o mecánicos moleculares. Por lo general, 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 borde son pequeñas mientras que los vértices están bien separados. Estos sistemas pueden realizar minimización basada en el descenso gradiente de una función energética, o pueden traducir las fuerzas directamente en velocidades o aceleraciones para los vértices en movimiento.
• Los métodos de diseño espectral utilizan como coordenadas los eigenvectores de una matriz como el Laplaciano derivado de la matriz de adyacencia del gráfico.
• Métodos de diseño ortogonal, que permiten que los bordes del gráfico funcionen horizontal o verticalmente, paralelamente a los ejes de coordenadas del diseño. Estos métodos fueron diseñados originalmente para problemas de diseño VLSI y PCB, pero también se han adaptado para el dibujo de gráficos. Por lo general implican un enfoque multifase en el que se planifica un gráfico de entrada reemplazando puntos de cruce por vértices, se encuentra una incrustación topológica del gráfico planarizado, se eligen orientaciones de borde para minimizar curvas, se colocan vértices consistentemente con estas orientaciones, y finalmente una etapa de compactación de diseño reduce el área del dibujo.
• Los algoritmos de diseño de árboles muestran una formación similar a los árboles, adecuada para los árboles. A menudo, en una técnica llamada "distribución de globos", los niños de cada nodo en el árbol se dibujan en un círculo que rodea el nodo, con los radios de estos círculos disminuyendo a niveles inferiores en el árbol para que estos círculos no se superponen.
• Los métodos de dibujo de gráficos de capa (a menudo llamado dibujo de estilo Sugiyama) son los más adecuados para gráficos o gráficos acíclicos dirigidos 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 Coffman-Graham, de tal manera que la mayoría de los bordes bajan de una capa a la siguiente; después de este paso, se organizan los nodos dentro de cada capa para minimizar los cruces.

• Los diagramas de arco, un estilo de diseño que data de la década de 1960, colocan los vértices en una línea; los bordes pueden ser dibujados como semicírculos arriba o debajo de la línea, o como curvas lisas unidas de múltiples semicírculos.
• Los métodos de distribución 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 pueden ser dibujados como acordes del círculo o como arcos dentro o fuera del círculo. En algunos casos, se pueden utilizar múltiples círculos.
• El dibujo Dominance coloca vértices de tal manera que un vértice es hacia arriba, hacia la derecha, o ambos de otro si y sólo si es accesible desde el otro vértice. De esta manera, el estilo de diseño hace visible la relación de accesibilidad del gráfico.

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 suele ofrecer el software de análisis de redes sociales
• Diagramas de Hasse, un tipo de dibujo gráfico especializado en pedidos parciales
• Dessin d'enfants, un tipo de dibujo gráfico utilizado en geometría algebraica
• Esquemas de Estado, representaciones gráficas de máquinas de estado finito
• Diagramas de red informática, representaciones de los nodos y conexiones en una red informática
• Flowcharts y drakon-charts, dibujos en los que los nodos representan los pasos de un algoritmo y los bordes representan el flujo de control entre pasos.
• Los 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 incluyendo árboles filogenéticos, redes de interacción proteína-proteína y vías metabólicas.

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 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 EDA. literatura. 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 las redes grandes dibujando 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 libre/libre biblioteca Python para el análisis de gráficos.
• Graphviz, un sistema de dibujo de gráficos de código abierto de AT plagaT Corporation
• Linkurious, un software de análisis y visualización de redes comerciales para bases de datos gráficas
• Mathematica, una herramienta de cálculo de propósito general que incluye herramientas de visualización de gráficos 2D y 3D y análisis de gráficos.
• Microsoft Automatic Graph Layout, open-source. Biblioteca NET (anteriormente llamada GLEE) para establecer gráficos
• Red X es una biblioteca Python para estudiar gráficos y redes.
• Tulip, una herramienta de visualización de datos de código abierto
• Sí. Ed, un editor de gráficos con funcionalidad de diseño de gráficos
• PGF/TikZ 3.0 con el graphdrawing paquete (requiere LuaTeX).
• LaNet-vi, un software de visualización de redes de código abierto
• Edraw Max 2D software de diagramación técnica de negocio