Thursday, March 5, 2015

Genetic Graph Drawing Algorithms: A Bibliography

This is a quick follow up to my previous post about genetic algorithms and a GA for bipartite graph drawing. What follows is a listing (not properly formatted, sorry) of papers I've found on the topic of genetic graph drawing. I included the paper discussed in the previous post as well. This area of graph drawing is pretty new to me, though some some promising areas of application seem to be in the visualization of bipartite graphs and lattice graphs. Apart from specific graph examples the approach also seems appealing in that one can explicitly hard code into the evaluation function things like symmetries, sum of edge lengths, maximum edge lengths,...etc. to be optimized in the graph drawing, essentially tailoring the desired output according to your own visual preferences. This contrasts with other common graph drawing techniques (e.g. spectral and force-directed methods) which model the graph drawing problem in terms of minimizing some energy function which can of course result in optimal values for said aesthetic parameters but don't explicitly make clear which ones will be optimized if any from the get go. For those readers who also find this topic interesting, happy reading! :-)

Genetic Graph Drawing Papers: 


  1. Peter Eades, Hugo A.D. do Nascimento, A Focus and Constraint-Based Genetic Algorithm for Interactive Directed Graph Drawing, The Second International Conference of Hybrid Intelligent Systems, 2002.
  2. Bernadete M.M. Neta, Gustavo H.d. Araujo, Frederico G. Guimaraes, Renato C. Mesquita, Petr Ya. Ekel, A fuzzy genetic algorithm for automatic orthogonal graph drawing, Applied Soft Computing 12, 2012
  3. Brian Loft and John Snow, A Genetic Algorithm for Drawing Ordered Sets, Texas College Mathematics Journal, Volume 3 Issue 2, 2006
  4. Hobbs and Rogers, Representing Space: A Hybrid Genetic Algorithm for Aesthetic Graph Layout
  5. Bernadete M. Mendonca Neta, Gustavo H. D. Araujo, Frederico G. Guimaraes, A Multiobjective Genetic Algorithm for Automatic Orthogonal Graph Drawing, ACM, 2011
  6. Salabat Khan, Mohsin Bilal, Muhammad Sharif, Farrukh Aslam Khan, A Solution to the Bipartite Drawing Problem Using Genetic Algorithm
  7. Rosete-Suarez, M. Sebag, A. Ochoa Rodriguez, A Study of Evolutionary Graph Drawing
  8. Qing-Guo Zhang, Hua-Yong Liu, Wei Zhang, Ya-Jiun Guo, Drawing Undirected Graphs with Genetic Algorithms, ICNC 2005
  9. Dhamyaa A. AL-Nasrawi, Najah A. Rabee, Ausay A. Ja’afar, Karrar I. Mohammed, Evolutionary Algorithm Implementation for Good Graph Drawing Using Fuzzy Fitness Function
  10. Gudenberg, Niederle, Ebner, Eichelberger, Evolutionary Layout of UML Class Diagrams
  11. Toshiyuki Masui, Evolutionary Learning of Graph Layout Constraints from Examples, Proceedings of the ACM Symposium on User Interface Software and Technology, 1994, ACM Press, pp 103-108
  12. Zoheir Ezziane, Experimental Comparison Between Evolutionary Algorithm and Barycenter Heuristic for the Bipartite Drawing Problem, Journal of Computer Science 3, Issue 9, 2007
  13. Mohamed A. El-Sayed, GA for straight-line grid drawings of maximal planar graphs, Egyptian Informatics Journal, 2012
  14. Erkki Makinen and Mika Sieranta, Genetic Algorithms for Drawing Bipartite Graphs, Department of Computer Science University of Tampere, Report A-1994-1
  15. Dana Vrajitoru and Boutros R. El-Gamil, Genetic Algorithms for Graph Layouts with Geometric Constraints
  16. HE, H., Sykora, O. and Makinen, E., 2007. Genetic Algorithms for the 2-page book drawing problem of graphs, Journal of Heuristics, 13 (1), pp. 77-93
  17. Behrooz Koohestani, Genetic Hyper-Heuristics for Graph Layout Problems, PhD Thesis, Department of Computer Science University of Essex, 2013
  18. Dana Vrajitoru, Multiobjective Genetic Algorithm for a Graph Drawing Problem
  19. Timo Eloranta and Erkki Makinen, TimGA: A Genetic Algorithm for Drawing Undirected Graphs, Divulgaciones Matematicas Vol. 9, No. 2, 2001, pp. 155-171
  20. Jiayu Zhou, Youfang Lin, Xi Wang, Visualization of Large-Scale Weighted Clustered Graph: A Genetic Approach, Proceedings of the Twenty-Third AAI Conference on Artificial Intelligence, 2006

No comments: