Deep dive into diagram layout engines: Minimizing hierarchical edge crossings

Nice writeup, easy to follow.<p>Regarding improvements to crossing minimization, we&#x27;re fans of Brandes and Köpf, &quot;Fast and Simple Horizontal Coordinate Assignment&quot; GD2001 that guarantees linear time and at most two bends per edge. (If anyone would like to implement this in Graphviz let us know!)<p>Regarding introducing additional constraints to address the problem that the algorithm &quot;doesn&#x27;t understand the sensible or hierarchical relationship between the blocks in my diagram&quot; we&#x27;re fans of Yoghourdjian, Dwyer et al, &quot;High-quality ultra-compact grid layout of grouped networks&quot; from IEEEVIS 2015. It looks quite difficult to implement. The figures in the paper took several minutes to generate and probably involved cutting and pasting between several tools.<p>A different approach was taken by Dwyer, Koren and Marriott, in &quot;IPSep-CoLa: An Incremental Procedure for Separation Constraint Layout of Graphs&quot; IEEEVIS 2006 where they introduce a kind of layering or asymmetry into force-directed energy models. This is implemented in Graphviz neato -Gmode=hier

My problem with automated diagram layouts has always been that the algorithm doesn&#x27;t understand the sensible or hierarchical relationship between the blocks in my diagram, which isn&#x27;t always the same as what the connectors are trying to show. The algorithm optimizes for the connectors (crossings), which certainly contributes to readability, but often at a cost to the overall readability of my diagram.

Has anyone seen anything that can automate the layout of a genealogy tree? It seems like a prime example of those impossible diagrams (if you show siblings and cousins, if you go only in one direction it becomes trivial).

I don’t like the approach of monetizing an algorithm. Once a FOSS competitor gets similar layout capabilities, this product is in trouble.

This is the same problem as PCB layout? What happens if you do a two layer board where each part has a few I&#x2F;Os and is a block of the flow chart?

This seems like an implementation of Sugiyama algorithm, how is this different?