Nice writeup, easy to follow.<p>Regarding improvements to crossing minimization, we're fans of Brandes and Köpf, "Fast and Simple Horizontal Coordinate Assignment" 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 "doesn't understand the sensible or hierarchical relationship between the blocks in my diagram" we're fans of Yoghourdjian, Dwyer et al, "High-quality ultra-compact grid layout of grouped networks" 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 "IPSep-CoLa: An Incremental Procedure for Separation Constraint Layout of Graphs" 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't understand the sensible or hierarchical relationship between the blocks in my diagram, which isn'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).