Entorno web para visualizar grafos preservando simetrías

Abstract

En el transcurso de este proyecto se desarrolló una aplicación web para dibujo automático y simétrico de grafos pequeños. Las herramientas existentes para el dibujo de grafos utilizan algoritmos que no tienen como objetivo realizar un representación simétrica, lo que resulta en grafos poco agradables estéticamente y dificulta la visualización al usuario. Una de las mayores complejidades radica en que el problema de detección de simetrías en grafos es NP-completo. Por ello, para la representación se utilizaron heurísticas basadas en el problema de partición de automorfismos, que tiene solución en tiempo cuasi-polinomial. Además, se contemplan criterios de estéticos de visualización. La aplicación presenta resultados apropiados en grafos de hasta aproximadamente 20 nodos y es compatible con LaTeX, siendo su uso en documentos y publicaciones la principal motivación. Se enfocó el desarrollo para una alta usabilidad y baja latencia. Para su validación, se realizó una prueba de usabilidad y un estudio de estrés, ambos con resultados satisfactorios.