Introducción

El Trazado de Grafos (Graph Drawing) es un área de la teoría de grafos que trata la construcción de representaciones geométricas para los grafos. Los distintos trazados de grafos que existen facilitan la comprensión y la visualización de la información representada en estas estructuras.

En la actualidad, múltiples áreas de la informática aplican el trazado de grafos. Por ejemplo, ingeniería del software (diagramas de estado, diagramas de flujo de datos, diagramas de clases, diagramas de módulos), bases de datos (diagramas de Entidad-Relación), gestión de proyectos (diagramas PERT), inteligencia artificial (diagramas de representación del conocimiento), telecomunicaciones (diagramas de redes de computadores), diseño VLSI, programación lógica (árboles SLD). En otros campos de la ciencia encontramos más aplicaciones: biología (arboles filogenéticos), química (simulación de estructuras moleculares), arquitectura (planos planta), etc. [Di Battista, 1998], [Nishizeki, 2004].

La Representación de Visibilidad es una representación geométrica de digrafos acíclicos planos en la que cada vértice se convierte en un segmento horizontal y cada arista en un segmento vertical siempre que no intercepte un segmento horizontal. El estudio de esta representación fue impulsado inicialmente por el diseño VLSI y problemas de compactación. Dentro del Trazado de Grafos, esta representación se utiliza como base para la obtención de trazados poligonales y ortogonales.

Este Trabajo Fin de Carrera tiene como objetivo principal desarrollar una aplicación que permita construir la representación de visibilidad y los trazados que se derivan de ella. Específicamente, tendremos un sistema informático que permita la ejecución de los algoritmos que construyen los siguientes trazados:

  • Representación de visibilidad.

  • Representación de visibilidad con restricciones.

  • Trazado poligonal ascendente.

  • Trazado poligonal ascendente con restricciones.

  • Trazado ortogonal plano.

  • Trazado de dominancia rectilíneo.

  • Trazado de dominancia poligonal.

También, la aplicación permitirá convertir un grafo en digrafo a través de la orientación de sus aristas.

Además, se podrán realizar las operaciones básicas de edición de grafos. Es decir, existirán las funcionalidades de agregar, eliminar, seleccionar, copiar, pegar y cortar elementos de un grafo. Al mismo tiempo, se podrán deshacer o rehacer estas operaciones. También, existirá la posibilidad de abrir o guardar un grafo editado a un archivo.

La ejecución de los algoritmos debe ser paso a paso, mostrando las estructuras y representaciones intermedias que se generan. El usuario podrá controlar la ejecución de cada algoritmo pudiendo avanzar o retroceder un paso, así como ir hasta el final de la ejecución o cancelarla. De este modo, se facilita el estudio y la comprensión de los algoritmos a los usuarios del sistema. En esta finalidad didáctica radica la principal diferencia entre esta aplicación y las que ya han sido desarrolladas en el área del Trazado de Grafos [Open Directory, 2011].