Deep dive into diagram layout engines: Minimizing hierarchical edge crossings | Hacker News Reader

Deep dive into diagram layout engines: Minimizing hierarchical edge crossings

terrastruct.com

70 pointsalixanderwang13 comments

Nice writeup, easy to follow.

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!)

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.

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.

interesting observation. Do you have an example of this? I think that hierarchical algorithms tend to try to find a flow of edges and build from there. For example, package dependencies.

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).

Maybe not _exactly_ what you're looking for but check out the Eclipse Layout Kernel (ELK for short).

https://www.eclipse.org/elk/

this is also bundled in D2

Do you mean connections to siblings? I'd assume that siblings and cousins would be identified by their position in the hierarchy and not necessarily by an edge between them. Definitely, having this edge between two nodes at the same level makes the problem harder, specially for edge routing that could lead to lots of crossings (depending on other possible connections you might want, like grandparent)

Well that's the difficulty, every time you have a wedding you are bringing in another tree, and the new spouse will have siblings and cousins that will have their own children and parents.

So I think a complete genealogy tree would be impossible to represent in 2d without crossing but most genealogy trees aren't that exhaustive so there must be an algorithm that creates a good representation when it is possible.

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

Hah, typically this line goes, "once Google/big tech does this, you're in trouble".

The reality is like that xkcd meme of some random dev in midwest US supporting critical infra with their open source efforts. GitHub natively runs Mermaid which runs Dagre, which has been unmaintained for many years now because the one guy working on it left and nobody's touched it since, despite many holes in the algorithm.

ELK has been continuously worked on by a research team for over a decade, and we can produce better looking layouts just by specializing for different cases. The space is so large. I hope that a great FOSS open-source layout engine comes along, I'll gladly integrate it into D2, but I don't fear it'll make TALA moot.

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

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

Yes, this article describes two algorithms from the 90's for the crossing reduction stage of the Sugiyama algorithm (which has a few other steps).

Reply on news.ycombinator.com