14

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?

user2722968
  • 13,636
  • 2
  • 46
  • 67

3 Answers3

9

You can make a topological sorting of the DAG to have the vertices sorted in a way that for every edge x->y, vertex x comes before than y.

Therefore, if you have a -> v, b -> v, you will get something like a, b, v or b, a, v.

Using this you can easily represents DAGs like this:

topological sorting

Arturo Menchaca
  • 15,783
  • 1
  • 29
  • 53
  • Hrms, I should have thought of that myself... While this approach is very simple and easily implemented: Is there actualy proof that the result is optimal with respect to edge crossings for any DAG ? – user2722968 Sep 28 '16 at 15:58
  • I've found out how to do a topological sort in `networkx`, but really has no clue how to draw in topological sorted order like the one in your answer. Could you give me some hints? – kawing-chiu Dec 18 '17 at 09:41
6

Yes, as @Arturo-Menchaca said a topological sorting may help to reduce overlapping count of edges. But it may be not optimal. There is no good algorithm for edge crossing minimization. Problem for crossing minimization is NP-complete. The heuristics are applied for solving this problem.

This StackOverflow link may help you: Drawing Directed Acyclic Graphs: Minimizing edge crossing?

I suppose your problem is related to an aesthetically pleasing way of the graph layout. Some heuristics are described in the articles Overview of algorithms for graph drawing, Force-Directed Drawing Algorithms. May be information about planar graph or almost planar graph can help you also.

Some review of the algorithms for checking and drawing planar graphs are described in the Wiki pages Planar graph, Crossing number (graph theory). The libraries and algorithms for planar graph drawing are described in the StackOverflow question How to check if a Graph is a Planar Graph or not? For example the author in the article GA for straight-line grid drawings of maximal planar graphs uses genetic algorithms for straight-line grid drawing.

Good descriptions for almost planar graphs are given in the articles Straight-Line Drawability of a Planar Graph Plus an Edge, On the Crossing Number of Almost Planar Graphs.

Try to modify the original algoritms using your condition with one axis alignment.

Community
  • 1
  • 1
Didgeridoo
  • 1,222
  • 2
  • 14
  • 21
3

If I understood you correctly then you want to minimize the number of edge-crossings in your graph layout. If so, then the answer is "No", because this problem is proved to be NP-complete in the general case. See this, "Crossing Number is NP-Complete, Garey, Johnson".

If you need a not an optimal but just good enough solution, there are multiple articles on this topic because it is heavily related with circuit layouts. Probably googling "crossing number heuristics" and looking through the abstracts of some papers will solve your task better then me trying to guess blindly your requirements.

Ivan Smirnov
  • 4,365
  • 19
  • 30