I've got a DAG of around 3.300 vertices which can be laid out quite successfully by dot as a more or less simple tree (things get complicated because vertices can have more than one predecessor from a whole different rank, so crossovers are frequent). Each vertex in the graph came into being at a specific time in the original process and I want one axis in the layout to represent time: An edge relation like a -> v, b -> v means that a and b came into being at some specific time before v.

Is there a layout algorithm for DAGs which would allow me to specify the positions (or at least the distances) on one axis and come up with an optimal layout regarding edge crossovers on the other?

  • $\begingroup$ Welcome to CS.SE! What does tree-like mean? Does it mean the graph is a dag, and most nodes have only one predecessor, but a few might have multiple predecessors? Does the edge relation have any connection with time? For instance, if we have an edge $u \to v$, does that mean that node $u$ necessarily (or usually) came into existence at a time before node $v$? Or is time totally unrelated to the predecessor/edge structure? Can you edit your question to clarify a bit further? $\endgroup$ – D.W. Sep 22 '16 at 6:29
  • $\begingroup$ I hope to have cleared things up $\endgroup$ – user2722968 Sep 22 '16 at 6:59
  • $\begingroup$ Can't you modify whatever algorithm dot uses, so that it doesn't change the initial $x$ position? It feels like any algorithm modified in that way would have a good chance of working. $\endgroup$ – David Richerby Sep 22 '16 at 8:15
  • $\begingroup$ You can tell dot that some edges don't count for the ranking (the constraint attribute iirc). $\endgroup$ – adrianN Sep 22 '16 at 9:39
  • $\begingroup$ I can't trivially use an algorithm that will assign nodes to the same grid coordinate on the Y-axis (and scale X to time) because that may lead to overlapping nodes. The algorithm has to pick up a given X-grid and work out the optimal Y-part $\endgroup$ – user2722968 Sep 26 '16 at 6:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.