Visualización de Grafos

Abstract

El dibujado de grafos direcciona el problema de visualizar información estructural o relacional construyendo representaciones visuales geométricas de grafos o redes que son los modelos subyacentes en una gran cantidad de datos abstractos. La generación automática del dibujo de un grafo tiene importancia en aplicaciones claves tales como la Ingeniería de Software, la Visualización de Información (VI), Data Mining, el diseño de Bases de Datos e Interfases Visuales, la Representación del conocimiento y las Telecomunicaciones entre otros dominios. Las representaciones pictóricas de grafos han sido una herramienta de modelado tradicional; fueron usadas intensivamente en forma manual y aún hoy siguen utilizándose de este modo. En la década del '60, los científicos en computación comenzaron a utilizar los dibujos de grafos como herramienta para el desarrollo de software. Knuth [Knu63] fue quizás el primero en presentar un algoritmo para dibujar grafos con propósitos de visualización. Actualmente, existen herramientas que permiten que muchas aplicaciones se beneficien, en alguna medida, de la generación automática de dibujos de grafos. Debido a la naturaleza combinatoria y geométrica de los problemas relacionados y al amplio espectro de los dominios de aplicación, la investigación sobre dibujado y visualización de grafos se ha desarrollado dentro de distintas áreas como la Matemática Discreta (teoría topológica de grafos, teoría geométrica de grafos, teoría de orden), el Diseño de Interfaces (lenguajes visuales, interfaces gráficas, visualización de software) y los Algoritmos (algoritmos de grafos, estructuras de datos, geometría computacional, sistemas de VI). Este trabajo presenta una descripción de la investigación realizada hasta el momento en visualización de grafos. En la próxima sección se detallan los elementos esenciales a tener en cuenta en el dibujado de los grafos con el objetivo de obtener una visualización efectiva; a continuación se hace una breve reseña y análisis de los distintos métodos para el dibujado de los mismos, concluyendo con una descripción del trabajo realizado hasta el momento.