3 ms·

So the author mentions hearing about the Reingold-Tilford Algorithm which wouldn't work for the example given since R-T is meant for binary trees and a family t

So the author mentions hearing about the Reingold-Tilford Algorithm which wouldn't work for the example given since R-T is meant for binary trees and a family tree might have more than 2 nodes. Which led me to wonder why is there even an "algorithm" per se for binary trees: wouldn't it be acceptable to just trace out a complete binary tree with spaces reserved for each potential node, and only fill in a space with a node if it is non-null? Or does this not meet some criterion of "niceness" for drawings?

captncraig 7y ago
If you do that, you quickly run into the feasible depth limit for what you can show in a fixed space. Especially for sparse trees. Consider something like family trees, where you generally don't know anything about certain lines, but may have 20 generations or more on selected lines. No way could you show 2^20 nodes in a fixed format rendering, but you can make something kinda pretty by eliminating the empty space and organizing things to fill it intelligently.
- taywrobel 7y ago
  I was just writing a radial RT-like visualization for displaying the branching structure of a binary tree and ran into the issue of information density you describe. Still pretty happy with the results, tho, in how it shows the structure and clustering. And I colored it like a tree, just for fun - https://giphy.com/gifs/TKFUkrWQtil60Ij2YJ/html5 https://giphy.com/gifs/TKFUkrWQtil60Ij2YJ/html5
raegis 7y ago
That only works for complete (or "nearly" complete) binary trees, and you can't draw many of these since the number of children in a generation grows exponentially. For most trees you have to try to keep the width minimal while avoiding collisions between deeply-nested left and right children. One of the earlier papers to give some precise "niceness" criteria is "Tidier Drawings of Trees" (https://reingold.co/tidier-drawings.pdf https://reingold.co/tidier-drawings.pdf) by Reingold and Tilford, with a companion Pascal program for computing the coordinates.
- virtuous_signal 7y ago
  Fantastic. I would not have thought that binary-tree-drawing could be such a complicated problem.
  - ygra 7y ago
    Graph drawing in general is a field full of complicated problems.

captncraig 7y ago

If you do that, you quickly run into the feasible depth limit for what you can show in a fixed space. Especially for sparse trees. Consider something like family trees, where you generally don't know anything about certain lines, but may have 20 generations or more on selected lines. No way could you show 2^20 nodes in a fixed format rendering, but you can make something kinda pretty by eliminating the empty space and organizing things to fill it intelligently.

taywrobel 7y ago
I was just writing a radial RT-like visualization for displaying the branching structure of a binary tree and ran into the issue of information density you describe. Still pretty happy with the results, tho, in how it shows the structure and clustering. And I colored it like a tree, just for fun - https://giphy.com/gifs/TKFUkrWQtil60Ij2YJ/html5 https://giphy.com/gifs/TKFUkrWQtil60Ij2YJ/html5

raegis 7y ago

That only works for complete (or "nearly" complete) binary trees, and you can't draw many of these since the number of children in a generation grows exponentially. For most trees you have to try to keep the width minimal while avoiding collisions between deeply-nested left and right children. One of the earlier papers to give some precise "niceness" criteria is "Tidier Drawings of Trees" (https://reingold.co/tidier-drawings.pdf https://reingold.co/tidier-drawings.pdf) by Reingold and Tilford, with a companion Pascal program for computing the coordinates.

virtuous_signal 7y ago
Fantastic. I would not have thought that binary-tree-drawing could be such a complicated problem.
- ygra 7y ago
  Graph drawing in general is a field full of complicated problems.