Genetic Algorithm to Draw a Graph? Position assignment problem

Question

I have an assignment problem at hand and am wondering how suitable it would be to apply local search techniques to reach a desirable solution (the search space is quite large).

I have a directed graph (a flow-chart) that I would like to visualize on 2-D plane in a way that it is very clear, understandable and easy to read by human-eye. Therefore; I will be assigning (x,y) positions to each vertex. I'm thinking of solving this problem using simulated annealing, genetic algorithms, or any such method you can suggest

Input: A graph G = (V,E)
Output: A set of assignments, {(xi, yi) for each vi in V}. In other words, each vertex will be assigned a position (x, y) where the coordinates are all integers and >= 0.

These are the criteria that I will use to judge a solution (I welcome any suggestions):

• Number of intersecting edges should be minimal,
• All edges flow in one direction (i.e from left to right),
• High angular resolution (the smallest angle formed by two edges incident on the same vertex),
• Small area - least important.

Furthermore; I have an initial configuration (assignment of positions to vertices), made by hand. It is very messy and that's why I'm trying to automate the process.

My questions are,

• How wise would it be to go with local search techniques? How likely would it produce a desired outcome?

• And what should I start with? Simulated annealing, genetic algorithms or something else?

• Should I seed randomly at the beginning or use the initial configuration to start with?

• Or, if you already know of a similar implementation/pseudo-code/thing, please point me to it.

Any help will be greatly appreciated. Thanks.

Answer 1

I don't think it is wise to use local search techniques. There are many (fast) methods which work pretty good for many classes of graphs. Of course you can also test local search methods.

A few comments:

• Number of intersecting edges should be minimal

Is your graph planar? If yes, there are many good methods for planar graphs (e.g. dominance drawings).

Is it a general digraph? In this case a hierarchical approach may be suitable (more information later).

• All edges flow in one direction (i.e from left to right)

Does it contain cycles? If yes, this is not possible.

A great source for graph drawing algorithms is Graph Drawing: Algorithms for the Visualization of Graphs.

In my opinion a good first approach to this problem is the hierarchical approach. Check the paper by Sugiyama et. al Methods for Visual Understanding of Hierarchical System Structures (chapter 9 in 1 describes such methods).

If you go with the local optimization methods, I would definitely use the initial configuration to start with (since it should be close to a good local optimum).

Answer 2

1. TimGA - A Genetic Algorithm for Drawing Undirected Graphs
2. A Numerical Optimization Approach to General Graph Drawing

I was given task similar to yours on my job. I used two things given above. Both the things work and should give you general idea. In the end you will have to do some tweaks that are specific to your graphs.

Answer 3

graphviz contains tools to make attractive planar layouts. the papers used to inform the programs are listed at http://www.graphviz.org/Documentation.php .

Answer 4

force-based methods are probably the most common for graph visualization but its possible that GAs (more recently investigated for this purpose) are effective & currently underexplored & hybrid GA-force based solutions are possible via force analysis in the fitness function. here are some other refs not cited so far

• GENETIC ALGORITHMS FOR GRAPH LAYOUTS WITH GEOMETRIC CONSTRAINTS Vrajitoru, El-Gamil

• Graph layout using a genetic algorithm Barreto, Barbosa

• Drawing Undirected Graphs with Genetic Algorithms Zhang, Liu, Zhang, Guo