| Graph | Graph Drawing | Drawing Directed Graphs | Drawing Undirected Graphs (2D 3D) |

Genetic Algorithm for Drawing Directed Graphs

Genetic algorithm (GA) is a stochastic global search method, which has proven to be competent for many kinds of optimization problems. They work by simulating the process of the creature’s evolution.

We developed a method based on induced sub-graphs, a subset of the vertices of a graph together with any edges whose endpoints are both in this subset, to overcome the disadvantage of traditional node-based methods, for example, traditional random selected crossover points seem generate a meaningless set to operate. In order to match the ideas, we designed a new data structure and modify genetic operations.

We adopted Sugiyama style to simplify this problem, especially a dummy node is inserted when the edge crosses a layer. The selected aesthetics constraints focus on decreasing the number of edge-crossing. Two resulting drawings of the system, “GeneDAGDrawing”, are illustrated below.

Further research will strive to emphasize the interaction between the software and human. At present most of similar systems, including “GDHints”, improve the performance by the interaction.