# Algorithms for laying out directed graphs?

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?

-
I'm curious, do the x-coordinates reflect the graph structure (as mentioned by David) or are they an independent variable? And do you have rough estimates for the number of nodes and edges? – Martin M. W. Nov 12 '09 at 22:06
Yes, they reflect the structure of the graph - to be specific, the x axis is time. The graph currently has about 86 nodes and 74 edges, but it will be growing. I estimate a total for both nodes and edges somewhere between 400 and 500. – Brent Hagany Nov 13 '09 at 1:21