title: Algorithm for drawing a graph structure?
body: <p>I have a digraph graph G=(V,E) that I would like to redraw because it is currently very messy. This is a flow chart that is being visualized and since |V|>1000 and each v in V has more than 1 outgoing edge, it is very hard to trace by eye. For instance; a node on the lower left corner is connected by an edge to a node on the upper right corner. It would be better, for example, if these two nodes were placed next to each other. There are too many edges and it is a pain to trace each of them.</p>
  
  <p>I have access to and can change the (x,y) coordinates of all the vertices. I would like to redraw G by maintaining it's current structure, in a way that is more human-friendly. I thought that minimizing the number of intersecting edges may be something to start with.</p>
  
  <p>Is there an algorithm that can help me redraw this graph?</p>
  
  <p>My question is, how do I assign (x,y) coordinates to each v in V such that it is organized better and easier to trace and read? How do I express these requirements formally? Should I go with a heuristic, if this is NP? <a href="http://www.islandone.org/MMSG/aasm/fig5-17.gif" rel="nofollow">Here</a> is an example for a somewhat organized graph and <a href="http://amatterofdegree.typepad.com/.a/6a00d83452791169e20133ee47a794970b-800wi" rel="nofollow">this</a> is something messy (although much smaller than what I'm dealing with).</p>
  
  <p>Any help will be greatly appreciated. Thanks.</p>
  
  <p><strong>EDIT:</strong> I'm still looking for a to-the-point answer. I've researched into planar straight-line and orthogonal drawing methods but what I've got is lengthy research papers. What I'm seeking is an implementation, pseudo-code or at least something to get me started.</p>
  
  <p><strong>EDIT 2:</strong> I'm not trying to display the graph. The input to the algorithm shall be the <code>graph G (composed of V and E)</code> and the output shall be <code>{(xi, yi) for each vi in V}</code></p>