How video games change through time is quite an interesting topic to be analyzed further. This research focuses on producing an animation of aesthetically-pleasing two dimensional (2D) undirected graphs based on a PC video games dataset to analyze it further and developing a web-based application for users to control and create the animation of graphs. To make an animation of graphs easier to understand, it is preferable that the changes between the displays of the previous period and the next period are as least as possible, thus allowing a user to grasp the changes of the graph’s structure faster. To tackle this problem, a Genetic Algorithm based undirected graph drawing that minimizes both aesthetic criteria and mental map cost is proposed in this research. The dataset used for this research is collected from GameFAQs.com on April, 24th 2019. After a preprocessing, it consists of 36,696 games data with the english titles from 1985 to 2019. Our experiment results proved that smoother animation can be achieved and information is indeed better preserved throughout the animation.

[1] Kamada, T., Kawai, S. “An Algorithm for Drawing General Undirected Graphs”. Information Processing Letters 31, pp. 7-15, 1989
[2] Fruchterman, T., Reingold, M., “Graph Drawing by Force-directed Placement”. Software – Practice and Experience 21, pp.1129-1164, 1991
[3] Eades, P., Lai, W., Misue, K., Sugiyama K., “Preserving the mental map
of a diagram”. in: Proceedings of Compugraphics 91, pp. 24–33, 1991.
[4] Davidson, R., Harel, D., “Drawing Graph Nicely using Simulated Annealing”. ACM transaction on graphics vol 15, pp. 301-331, 1996
[5] Alejandro, S., Alberto, R., Michèle, S., “Automatic Graph Drawing and Stochastic Hill Climbing”, GECCO, pp 1699-1706, 1999
[6] J. Branke, F. Bucher, and H. Schmeck, “Using genetic algorithms for drawing undirected graphs”, The Third Nordic Workshop on Genetic Algorithms and their Applications, 1998.
[7] Barreto, A., Barbosa, H., “Graph Layout Using a Genetic Algorithm”, Proceedings. Vol.1. Sixth Brazilian Symposium on Neural Networks, 2000
[8] Pinaud, B., Kuntz, P., Lehn, R., “Dynamic Graph Drawing with a Hybridized Genetic Algorithm”, Adaptive Computing in Design and Manufacture VI, pp.365-375, 2004
[9] Zhang QG., Liu HY., Zhang W., Guo YJ. “Drawing Undirected Graphs with Genetic Algorithms”, Advances in Natural Computation. ICNC 2005
[10] Qu JH., Liu XY., Sun MH., Qi Feng, “GPU-Based Parallel Particle Swarm Optimization Methods for Graph Drawing”, Discrete Dynamics in Nature and Society, 2017
[11] Dib, FK., Rodgers, P., “Graph drawing using tabu search coupled with path relinking”, PLoS ONE 13(5), 2018
[12] Diehl, S., Gorg, C., “Graphs, They Are Changing Dynamic Graph Drawing for a Sequence of Graphs”, LNCS 2528, pp 23-31, 2002
[13] Frishman, Y., Tal, A., “Dynamic Drawing of Clustered Graphs”, Symposium on Information Visualization, 2004
[14] Bergman, D.S., “Mental map preservation principles and related measurements for quantitative evaluation of force-directed graph layout algorithm behaviour”, 2010
[15] Bridgeman, S., Tamassia, R., “A User Study in Similarity Measures for Graph Drawing”, JGAA, 6(3) pp 225-254, 2002
[16] Archambault, D., Purchase, H.C., “The Mental Map and Memorability in Dynamic Graphs”, Pacific Visualization Symposium, 2002
[17] Mediana, A., Hong SH., Eades, P., “New Quality Metrics for Dynamic Graph Drawing”, Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization, 2020
[18] Lee YY., Lin CC., Yen HC., “Mental map preservation using simulated annealing”, Asia Pacific Symposium on Information Visualization pp 179-188, 2006
[19] Robert Gove. "It Pays to Be Lazy: Reusing Force Approximations to Compute Better Graph Layouts Faster." Proceedings of Forum Media Technology, 2018. Retrieved from github: https://github.com/rpgove/greadability
[20] Resende M.G.C., Ribeiro C.C. “Path-relinking”. In: Optimization by GRASP. Springer, New York, NY. https://doi.org/10.1007/978-1-4939-6530-4
[21] Walter, M., “Interactive Visualization of Evolving Force-Directed Graphs” DUXU / HCII 2013 part IV pp 553-559, 2013
[22] Gower, J. C., “Generalized procrustes analysis”., Psychometrika. 40 (1), pp. 33-51., 1975
[23] Olga Kravchenko, “(Generalized) Procrustes analysis with Python/NumPy”, https://medium.com/@olga_kravchenko/generalized-procrustes-analysis-with-python-numpy-c571e8e8a421, Accessed on December 18, 2020
[24] “SciPy Spatial Procrustes, a similarity test for two data sets.”, https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.procrustes.html, Accessed on December 18, 2020
[25] “The Movie Dataset”, https://www.kaggle.com/rounakbanik/the-movies-dataset, Accessed on January 03, 2021