Ask HN: Dense Tree Layout Algorithms

44 points · bwestergard · 22 days ago

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.

18 comments

GistNoesis · 19 days ago

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

JohnKemeny · 19 days ago

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/

Show replies

graphviz · 18 days ago

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

atzeus · 19 days ago

This is a great index of algorithms for drawing trees:

https://treevis.net/

Show replies

brudgers · 20 days ago

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.

Show replies