Skip to main content
edited tags
Link
Jose Brox
  • 3k
  • 5
  • 38
  • 51
Source Link

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?