Ask HN: Dense Tree Layout Algorithms | Hacker News Reader

Ask HN: Dense Tree Layout Algorithms

44 pointsbwestergard18 comments

I recently bought a poster which features a really beautiful rendering of a phylogenetic tree of the world's bird families (a rooted binary tree).

https://lynxnaturebooks.com/product/orders-and-families-of-the-birds-of-the-world-poster/

I am sure it was carefully designed by hand. What algorithms could automatically generate a layout like this? The graphviz layout algorithms are poorly suited to the problem because they cannot seem to avoid edge/node coincidence beyond a certain node density.

View on HN

You can have look at Keenan Crane's repulsive curves https://www.cs.cmu.edu/~kmcrane/Projects/RepulsiveCurves/ind... (He also has various other interesting geometry projects if you have some time to wander https://www.cs.cmu.edu/~kmcrane/).

The domain is simply called Graph Drawing. There are no simple algorithm that guarantees some aesthetic outcome, but still, a lot is known in this domain.

To learn more, check out the Graph Drawing conference, or more specifically, their annual contests. Here are a few of the past contests:

* '24 https://mozart.diei.unipg.it/gdcontest/2024/results/

* '23 https://mozart.diei.unipg.it/gdcontest/2023/results/

* '22 https://mozart.diei.unipg.it/gdcontest/contest2022/results.h...

* '21 https://mozart.diei.unipg.it/gdcontest/contest2021/index.php...

* '20 https://mozart.diei.unipg.it/gdcontest/contest2020/results.h...

... and many more via the past contests history page: https://mozart.diei.unipg.it/gdcontest/history/

These graphs look very much hand-tuned.

Shouldn't the domain be called "Automated Graph Drawing"?

IIRC Tamara Munzner and some colleagues worked on visualizing large phylogenic trees.

There's this, too, https://academic.oup.com/mbe/article/33/8/2163/2579233 and it's implemented at http://phylo.io

This is a great index of algorithms for drawing trees:

https://treevis.net/

The paper for "Space-Reclaiming Icicle Plot (2020)" looks like it's going into the right direction. A space-reclaiming tree layout would be even better.

Algorithms can make many types of decisions, but an algorithm cannot make aesthetic decisions. The size of nodes and the size of the boundary are aesthetic decisions as is the ordering of the nodes and so on.

Or to put it another way, you do it by hand when you care and with a computer when you are meeting a specification.

The choice and design of algorithm can itself be an aesthetic decision. Eg, OP generated some layouts, and spotted something that wasn't to their taste; the edges frequently overlap. So, we might approach the problem like this:

1. Choose an arbitrary algorithm to lay out trees where the edges don't overlap. There's many ways to do this, it doesn't need to be legible at this step.

2. Insert additional nodes along each edge. How many nodes is a tuning parameter we'll need to play with.

3. Use a traditional force-based graph layout algorithm, one that assigns charge to the nodes so that they repel each other. Because we've given the edges some nodes, they will have charge and won't bunch up together.

4. (Optional?) Detect edge overlaps. If they exist, randomize the initial state and try again.

(Note that the algorithm I've described is O(n^2). Patience will be necessary. You can probably refine it further, I only thought about it for a few minutes. Optimizations applied to physics engines (collision detection, gravity simulation) will apply.)

I've dabbled in generative art like this, and if you're willing to do the math and programming and iterate on the design, you can definitely get something of the aesthetic you are after. Bonus, the skills are transferrable to some other kinds of programming, like property testing and graphics.

You won't get edge overlaps if you start with a non-crossing drawing. In addition, n² is not very much when you have <100 nodes, as in this case.

Force directed layout algorithms can also be made faster using quad-trees and approximate repulsion.

That's very similar to an algorithm I played with many years ago.

I also used simulated annealing, where a temperature controls the amount of random movement each node gets on an iteration, and the temperature is gradually reduced. It was a DAG though, not a tree.

For this particular example, I feel like a combination of both human input + algo could work. Something like:

* Have graphviz or some other solver output the [x;y] pairs for each vertex.

* Use the initial positions to create, with a physics engine, a construct where vertices are masses connected by springs following the DAG.

* Add a resizable bounding box constraint around the whole thing.

* Push and pull the boundaries and masses until you get something nice.

What you say still applies: you may want to give the user the ability to resize the masses and re-run the layout algorithm, etc.

I feel like a combination of both human input + algo could work.

For some definitions of “work” I agree.

But, a premise of the OP’s question seems to be a how-hard-could-it-be.

The color of the birds matters. That’s how hard aesthetics is. The shape matters too, for anyone who missed my larger point…and their names because the text is a graphic element.

And all the negative space.

If you want an analogy, there aren’t general purpose algorithms that solve 3-sat in the way we want it solved. Good solutions to specific problems require hand crafting a procedure tailored to the data.

I feel like we are, overall, in agreement, although this may be a case of [1] :-).

1: https://youtu.be/XHO4Aby6fT8?t=11

We are not in agreement about this particular example because it was made with care.

> but an algorithm cannot make aesthetic decisions

A constraint or score based process can be given rules for what bad aesthetic decisions are, like nodes too packed in one area, lines between nodes too long, edges shouldn't cross or if that is unavoidable should cross as little as possible, etc, so it can try to avoid them. The process of picking a more optimal solution by judging against these rules might be to apply some randomness and rerun many times, picking the best scoring result, or it might be by moving things around randomly from one start position to see if that improves the score, or both these methods can be applied. Without random factors in the main placement algorithm, reordering how nodes that have no particular precedence (say you have a node with three children that have no property indicating any of them should be ordered/positioned in any particular way with respect to the others visually), reordering how these nodes are passed to some layout functions can have a significant effect, again to be judged against the rules/constraints/scores specified.

This won't be perfect for all inputs, or even many inputs, but it can often produce a good enough result to be made perfect with a bit of human post-processing.

I've definitely seen a demo of this sort of process bing used interactively to layout mind-map drawings, though irritatingly I can't find it ATM to link to. In that the base algorithm ran a few processes, picked one of the results, and from there the human could pull things around, and it had a few controls for how other nodes could be moved in response to any change you made, or if it just warned that parts or the whole might benefit from reflow, or if it blocked the user from making certain changes, or if it stepped back completely at this point and let the user have full control with no further assistance. Of course this might be overkill most of the time: letting the algorithm do the first cut then giving the human full control of post-process tweaks is usually going to be sufficient.

> you do it by hand when you care and with a computer when you are meeting a specification

And for a compromise third option: let the computer do the initial leg work, leave it alone if that result is good enough, and change by hand to refine otherwise.

I use elk for automatic graph layout in my apps

Try yfiles via yed!

Scdvvg

Reply on news.ycombinator.com