El concepto de diseño de gráficos

Un gráfico es una estructura de datos que representa un conjunto de entidades, denominadas nodos, conectados mediante un conjunto de enlaces. A los nodos también se les denomina vértices. A los enlaces también se le denomina aristas o conexiones. En las aplicaciones prácticas, frecuentemente se utilizan gráficos para modelar un gran número de cosas: redes informáticas, estructuras de programas de software, diagramas de gestión de proyectos, etc. Los gráficos son modelos muy eficaces porque permiten que las aplicaciones se beneficien de los resultados de la investigación en el campo de la teoría de grafos. Por ejemplo, existen métodos muy eficientes para buscar el camino más corto entre dos nodos, el camino de coste mínimo, etcétera.

Diseño de un gráfico

Se utiliza en las interfaces de usuario gráficas de aplicaciones que necesitan mostrar modelos de gráficos. Diseñar un gráfico significa dibujar el gráfico de modo que se genere una representación adecuada y legible. Básicamente, esto implica determinar la ubicación de los nodos y la forma de los enlaces. Para algunas aplicaciones, la ubicación de los nodos ya se conoce (por ejemplo, a partir de posiciones geográficas de los nodos). Para otras aplicaciones, la ubicación no se conoce (un gráfico “lógico” puro) o sí se conoce, pero si se utiliza, generaría un dibujo del gráfico ilegible. En estos casos, debe calcularse la ubicación de los nodos.
¿Qué se entiende por representación “adecuada” de un gráfico? En las aplicaciones prácticas, para la representación del gráfico a menudo es necesario observar determinados criterios de calidad. Estos criterios pueden variar en función del campo de aplicación o de un estándar determinado de representación. Suele ser difícil decir qué en que consiste un buen diseño. Cada usuario puede tener distintos criterios, subjetivos, de lo que considera que es un “buen” diseño. Sin embargo, existe un objetivo común tras todos los criterios y estándares: la representación debe ser fácil de entender y permitir una navegación sencilla a través de la estructura compleja del gráfico.

¿Qué es un buen diseño?

Para hacer frente a las necesidades de distintas aplicaciones, se han desarrollado muchas clases de algoritmos de diseño de gráficos. Un algoritmo de diseño aborda uno o más criterios de calidad, según el tipo de gráfico y las características del algoritmo, al diseñar un gráfico.
Los criterios más comunes son estos:
  • Minimizar el número de link crossings
  • Minimizar el área total del dibujo
  • Minimizar el número de curvas (en dibujos ortogonales)
  • Maximizar el ángulo más pequeño formado por enlaces incidentes consecutivos
  • Maximizar la visualización de simetrías
¿Cómo puede satisfacer un algoritmo de diseño los criterios de calidad y los estándares de representación? Si examina cada uno de los criterios, algunos se pueden satisfacer con facilidad, al menos para algunas clases de gráficos. Para otras clases, puede ser difícil generar un dibujo que cumpla los criterios. Por ejemplo, minimizar el número de intersecciones de enlaces es relativamente simple para los árboles (es decir, gráficos sin ciclos). Para gráficos generales, minimizar el número de intersecciones de enlaces es un problema matemático NP-complete (es decir, con todos los algoritmos conocidos, el tiempo necesario para ejecutar el diseño aumenta rápidamente conforme lo hace el tamaño del gráfico).
Si desea satisfacer varios criterios al mismo tiempo, puede que no exista una solución óptima para todos ellos, ya que muchos de los criterios se contradicen mutuamente. Hay que llegar a un compromiso sobre el tiempo que se puede dedicar a buscar la solución. Además, asignar pesos a cada criterio no es una tarea trivial. La optimización de varios criterios a la vez es, la mayoría de las veces, una tarea demasiado compleja y que lleva demasiado tiempo. Por ello, los algoritmos de diseño suelen estar basados en métodos heurísticos y puede que ofrezcan soluciones menos óptimas con respecto a uno o varios criterios. Afortunadamente, en la práctica, los algoritmos de diseño a menudo proporcionan representaciones razonablemente legibles.

Métodos para utilizar algoritmos de diseño

Los algoritmos de diseño pueden utilizarse de varias formas en las distintas aplicaciones en que se utilizan. Las formas más habituales de utilizar un algoritmo son:
  • El algoritmo de diseño lo hace todo sin la intervención del usuario, excepto quizás la elección del algoritmo de diseño que se va a utilizar. A veces, puede programarse un conjunto de reglas para elegir automáticamente (y dinámicamente) el algoritmo de diseño más adecuado para el tipo concreto de gráfico que se va a diseñar.
  • El usuario de la aplicación puede mejorar libremente el resultado del procedimiento de diseño automático a mano. En algunos casos, el usuario puede mover y “fijar” nodos en las posiciones que desee y volver a ejecutar el diseño. En otros casos, una parte del gráfico se establece automáticamente como “de sólo lectura” y el usuario puede modificar el resto del diseño.
  • Diseño desde cero
    El algoritmo de diseño se rehace del todo (“desde cero”) cada vez que el gráfico se modifica.
  • Diseño incremental
    Cuando el algoritmo de diseño se ejecuta por segunda vez en un gráfico modificado, intenta conservar la estabilidad del diseño en la medida de lo posible. El diseño no se vuelve a ejecutar desde cero. El algoritmo de diseño también intenta ahorrar tiempo de CPU utilizando el diseño anterior como solución inicial. Algunos algoritmos y estilos de diseño son incrementales por naturaleza. En otros casos, el diseño incremental puede ser imposible.