title: Genetic Algorithm to Draw a Graph? Position assignment problem
body: <p>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).</p>
  
  <p>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</p>
  
  <p><strong>Input:</strong> A graph G = (V,E)<br>
  <strong>Output:</strong> A set of assignments, <code>{(xi, yi) for each vi in V}</code>. In other words, each vertex will be assigned a position (x, y) where the coordinates are all integers and >= 0.</p>
  
  <p>These are the criteria that I will use to judge a solution (I welcome any suggestions):</p>
  
  <ul>
  <li>Number of intersecting edges should be minimal,</li>
  <li>All edges flow in one direction (i.e from left to right),</li>
  <li>High angular resolution (the smallest angle formed by two edges
  incident on the same vertex),</li>
  <li>Small area - least important.</li>
  </ul>
  
  <p>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.</p>
  
  <p>My questions are,  </p>
  
  <ul>
  <li><p>How wise would it be to go with local search techniques? How likely
  would it produce a desired outcome?  </p></li>
  <li><p>And what should I start with? Simulated annealing, genetic algorithms
  or something else?</p></li>
  <li><p>Should I seed randomly at the beginning or use the initial
  configuration to start with?</p></li>
  <li><p>Or, if you already know of a similar implementation/pseudo-code/thing, please point me to it.</p></li>
  </ul>
  
  <p>Any help will be greatly appreciated. Thanks.</p>
  
  <p><strong>EDIT:</strong> 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.</p>