Hacker Remix

Ask HN: Dense Tree Layout Algorithms

42 points by bwestergard 4 days ago | 18 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.

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

graphviz 10 hours 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

JohnKemeny 2 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/

amelius 2 days ago

These graphs look very much hand-tuned.

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

atzeus 2 days ago

This is a great index of algorithms for drawing trees:

https://treevis.net/

tauchunfall 1 day ago

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.