Genetic Algorithm to Draw a Graph? Position assignment problem 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.
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).