6
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Martin M. W.
    Commented Nov 12, 2009 at 22:06
  • $\begingroup$ 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. $\endgroup$
    – Brent Hagany
    Commented Nov 13, 2009 at 1:21

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Excellent, thank you! I think I am more familiar with the other meaning of layered graph drawing - it would have never occurred to me to search for that. I'm not too concerned about finding the absolute minimum number of crossings, so I think I should be able to avoid any NP-hardness. Anyway, I appreciate it. $\endgroup$
    – Brent Hagany
    Commented Nov 13, 2009 at 1:30
2
$\begingroup$

The documentation for GraphViz (a software package that does this sort of thing) has a number of papers on the subject included.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .