A Technique for Drawing Directed Graphs

Summary of the document : A Technique for Drawing Directed Graphs 

The goal of this paper is having high-quality directed graphs in a quickly way. These four phases describes the algorithm that draws directed graphs.

1. Placing nodes in discrete ranks 
2. Ordering nodes within ranks to reduce crossings 
3. Finding optimal coordinates for nodes 
4. Making splines to draw edges

There are some aesthetic principles that they want to follow as much as possible:

1. Expose hierarchical structure in the graph
2. Avoid visual perversions like edge crossing and sharp bends.
3. Keep edges short
4. Favor symmetry and balance

And also for making optimal rank assignment:

1. Making the graph acyclic: Breaking cycles by reversing certain edges which is based on depth- first search.
2. Problem definition:  To make short edges, according to aesthetic principle 3, it is needed to find an optimal node ranking.  
3. Network simplex:  They described a simple approach to the problem based on network simplex formulation.

Link to the documentation: http://www.graphviz.org/Documentation/TSE93.pdf