Minimise edge crossings in Hierarchical Layout

Question

I have been creating hierarchical directed graphs in yEd 3.20.1.  I've set the parameters to the default settings for Hierarchical layout (e.g. not using drawing as sketch, not selected elements incrementally), the only default setting that has been changed is to make the edge routing style polyline.

However, the resulting layouts clearly do not minimise the number of edge crossings. By eye, one can make several changes which reduces the number of crossings.  If I manually change these and run layout again it reverts to the sub-optimal layout.

I've attached an example.

Any suggestions on how to improve the layouts, so that obvious unnecessary edge crossings are eliminated?

Thanks

Example with unnecessary edge crossings

Manually adjusted layout with 8 fewer crossings

Further examples for which increasing the Maximal Duration does not resolve the problem:

New graph with unnecessary crossings

Manually adjusted with two fewer crossings

Comments

Can you upload a modified version of your diagram with those obvious manual changes? Please either edit your original question or add an answer in this thread for the upload. (I.e. please do not start a separate thread.)

---

Thanks - I've uploaded my previous graph in the original post with a couple of manual changes (repositioning KS55 & KS50 which were on the far left of the 5th & 6th rows, and moving Har85 on the bottom row (and two of the nodes that link to it)).  This has reduced the total number of edge crossings by 8.
However, if I run Hierarchical layout on this manually adjusted graph, it reverts to the less efficient layout.

Answer 1

Thank you very much for the additional information.

Let me start by addressing your second remark regarding hierarchical layout reverting to the less efficient result. That is the intended behavior. If the options "Selected Elements Incrementally" and "Use Drawing As Sketch" on tab "General" are turned off (which they are by default and which they should be for first time arrangements), the positions of elements prior to the layout calculation have no effect on the result.

What you can do, though, is the following: Run the hierarchic layout with "Selected Elements Incrementally" and "Use Drawing As Sketch" turned off, then manually move elements to more favorable positions (does not have to be pixel-perfect), then run the hierarchic layout again but this time with "Use Drawing As Sketch" turned on. "Use Drawing As Sketch" will try to respect relative positions from the input graph. In other words, if you turn on "Use Drawing As Sketch", "Har 85" will stay between "CoL 85" and "Ea 85" for the second layout calculation (its exact coordinates will be changed, though).

That said, the two-pass approach is not necessary for your example graph. In your case, it suffices to increase the "Maximal Duration" for the layout calculation. By default, the duration is set to 5 seconds. Increasing that to 60 seconds, I got this result. The algorithm did not even run noticeably longer with the increased duration. So, why did this help nonetheless? Hierarchical layout runs in separate phases and we conducted empirical tests to determine for each phase its "typical" percentage of the overall runtime. The maximal duration is then split among the phases according to their typical percentages. In your case, the edge crossing optimization phase seems to require more than its typical share of runtime, while other phases require less. Increasing maximal duration allowed the edge crossing minimization to calculate a better result without increasing runtime for other phases.

Comments

Thanks for your help - that's great.

---

I'm sorry to come back to you again.  While increasing the maximal duration, resolved the problems for the graph I initially sent you, I then added a few more nodes.  I've uploaded two more diagrams to my original question.  There is an obvious reduction in crossings possible to the automatic layout, but no matter how long I set the maximum run time, the Hierarchical layout algorithm does not seem to find it.
Is there a limit to the complexity of the graph for which the minimal crossings algorithm will work?

---

Thank you very much for the additional samples.

This is a special case which is already on our list of improvements for the hierarchic layout. While this looks like an easy problem to solve (for a human), it is very complex to solve in the algorithm. (Besides, the problem is only easy to solve for a human, because the algorithm already did a perfect job for the sub-tree below "CoL&WS 74".)

Regarding your question if there is a limit to the complexity for crossing minimization, well, theoretically no. However, crossing minimization is a computationally hard problem which means there is no algorithm that is able to compute an optimal solution in reasonable time. For this reason, such problems are solved using heuristics that produce good (but not perfect) results in reasonable time.
Your graph is an example of a case, where the heuristic does produce a good but not perfect result. (You need to keep in mind that your manual arrangement reduces the number of crossings from 41 to 39. That is less than 5% improvement.)

---

Thank you once again for your help.  I appreciate this is an NP hard problem, so no algorithm is likely to be able to find an optimal solution in complex cases.
What is strange for my examples is that I also ran them on yEd live - in the first example I gave, yEd live did not find the improvement achievable by increasing duration in yEd 3.20.  However, for the second set of examples yEd live found a much better layout, with only 29 crossings.

---

The crossing minimization is a (seeded) randomized algorithm. The algorithm uses the random number generator (RNG) of the underlying programming platform. For the desktop application this means the Java RNG is used, while for yEd Live the browser's JavaScript RNG is used. This results in a different sequence of random numbers which in turn results in a different sequence of nodes. This also means that yEd Live may produce worse results than yEd desktop for other graphs.