I have an acyclic digraph that I would like to draw in a pleasing way, but I am having trouble finding a suitable algorithm that fits my special case. My problem is that I want to fix the x-coordinate of each vertex (with some vertices having the same x-coordinate), and only vary the y. My aesthetic criteria are (in order of importance):


1. Ensure no two vertices are too close together
2. Minimize edge crossings and near misses
3. Make a reasonable use of the entire drawing space


I have tried several (modified) force-directed algorithms, but they haven't met my expectations on at least one of these - usually too many edge crossings.


Has anyone come across a problem like this, or can you point me to some good papers that deal with restrictions like this?



Algorithms for laying out directed graphs?
If the x-coordinates are compatible with the acyclic structure of your DAG (that is, for an edge u->v, the x coordinate of u should always be less than that of v) then this is a standard problem in graph drawing, known as Sugiyama-style layered drawing. (Usually it is the y coordinates that are fixed but that makes no difference.) Some versions of the problem (e.g. finding the exact minimum number of edge crossings) can be NP-hard but effective heuristics are known. See e.g. chapter 9 of Di Battista, Tamassia, and Eades, "Graph Drawing: Algorithms for the Visualization of Graphs", Prentice-Hall, 1999.


Searching Google scholar for "layered graph drawing" should also turn up some more recent references, but be careful that some of them (including mine) which use the term to mean something unrelated.


