Implementación web de un visualizador de grafos en dos dimensiones utilizando algoritmos genéticos

Abstract

El objetivo del presente trabajo de investigación es la implementación de una aplicación capaz de realizar despliegues de grafos en dos dimensiones, minimizando la cantidad de cruces y otras medidas de calidad. Para la implementación de la interfaz se utilizó el framework web Django. Se utilizó un algoritmo genético para la minimización de la ecuación de energía del grafo, ya que el cálculo de derivadas para los métodos clásicos de optimización no eran viables. Finalmente se realizaron diversas pruebas visuales y de rendimiento para encontrar los parámetros adecuados para la ecuación de energía y el algoritmo genético. Los resultados obtenidos de las pruebas realizadas permitieron documentar que las medidas de calidad importantes a tomar en cuenta para la ecuación de energía son los cruces entre arcos, la simetría del grafo y el ángulo formado por las aristas de un mismo vértice.