关键词: 遗传算法 无向图 画图 美学标准

Abstract:

This paper proposes a new genetic algorithm for drawing general undirected graphs nicely. Previous undirected graph drawing algorithms draw large cycles with no chords as concave polygons. In order to overcome such disadvantages, the genetic algorithm in this paper designs a new mutation operator call edsinglenodeneighborhood mutation, and adds a component aiming at symmetric drawings to the fitness function, and it can draw such type of graphs as co nvex polygons. The new algorithm has the following advantages： It is simple and easy to be implemented, and the figures drawn by the algorithm are beauutiful, and also it is flexible in that the relative weights of the criteria can be changed. The experiment results show that the figures drawn by our algorithm are more beautiful than that of simple genetic algorithms under the same conditions.

Key words: （genetic algorithm, undirected graph, graph drawing, aesthetic criteria）