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.

EDIT: It doesn't need to be fast - not in real-time. Furthermore; |V|=~200 and each vertex has about 1.5 outgoing edges on average. The graph has no disconnected components. It does involve cycles.

Answer 1

I would suggest looking at http://www.graphviz.org/Theory.php since graphviz is one of the leading open source graph visualizers.

Depending on what the assignment is, maybe it would make sense to use graphviz for the visualization altogether.

Answer 2

This paper is a pretty good overview of the various approaches. Roberto Tomassia's book is also a good bet.