4-pass approach to layout directed graphs

• Assign optimal rank to nodes to reduce edge length by using network simplex algorithm to solve
  min (SUM[rank w - rank v : (v,w) is an edge])
  subject to: rank w - rank v exceeds 1

  
  

• Set vertex order within rank based on heuristic for local transpositions to reduce crossing
  heuristics:

  (i) order a vertex by median position of its parents

  (ii) biase median to side where vertices are more closely packed

  (iii) swap adjacent vertices to reduce crossings

  
  

• Assign optimal coordinates to nodes to help keep edges straight

  
  

• Make splines to draw the links