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):

- Ensure no two vertices are too close together
- Minimize edge crossings and near misses
- 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?