Drawing Directed Acyclic Graphs: Minimizing edge crossing?
- by Robert Fraser
Laying out the verticies in a DAG in a tree form (i.e. verticies with no in-edges on top, verticies dependent only on those on the next level, etc.) is rather simple without graph drawing algorithms such as Efficient Sugimiya. However, is there a simple algorithm to do this that minimizes edge crossing? (For some graphs, it may be impossible to completely eliminate edge crossing.) A picture says a thousand words, so is there an algorithm that would suggest:
instead of:
EDIT: As the picture suggests, a vertex's inputs are always on top and outputs are always below, which is another barrier to just pasting in an existing layout algorithm.
