A. Martínez-Gavara, T. Pastore, R. Martí, P. Festa
El dibujo de grafos tiene numerosas aplicaciones, entre las que podemos destacar el análisis de datos, que requieren del uso de herramientas automáticas de representación. Existen numerosos criterios estéticos para obtener una buena representación de un grafo, siendo la reducción del número de cruces el más importante. El área del dibujo de grafos es muy activa y podemos encontrar en la literatura científica numerosos trabajos en los que la suma total del número de cruces se modeliza y resuelve como un problema de optimización. En esta charla nos centramos en una variante propuesta recientemente, que consiste en la minimización del máximo número de cruces sobre el conjunto de las aristas. Para su resolución, proponemos un algoritmo heurístico basado en la búsqueda Tabú que obtiene soluciones de alta calidad en tiempos de computación pequeños, como requieren las aplicaciones de dibujo. Los experimentos computacionales comparan nuestro algoritmo con los publicados anteriormente.
Palabras clave: metaheuristicos, dibujo de grafos
Programado
GT9-1 Heurísticas
4 de septiembre de 2019 10:40
I3L9. Edificio Georgina Blanes