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.
No comments:
Post a Comment