HACKER Q&A
📣 bwestergard

Dense Tree Layout Algorithms


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.

  👤 GistNoesis Accepted Answer ✓
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
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/

👤 graphviz
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
This is a great index of algorithms for drawing trees:

https://treevis.net/

👤 brudgers
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.

👤 klysm
I use elk for automatic graph layout in my apps
👤 w10-1
Try yfiles via yed!
👤 09674016976
Scdvvg