Tidier Drawings of Trees [pdf]

http://emr.cs.iit.edu/~reingold/tidier-drawings.pdf

by _virtu • 11 years ago

31 18 11 years ago

emr.cs.iit.edu

mstolpm• 11 years ago

Title should contain (1981).

I needed to draw tidy binary trees recently. I found the algorithm in this paper impenetrable, but the paper from which this one is derived (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.150...) had a very accessible algorithm, that produced results that I found acceptable.

soegaard• 11 years ago

There are some improvements in Buchheim et al:

; http://dirk.jivas.de/papers/buchheim02improving.pdf

See also "Compact layout of Layered Trees".

Note that Bill Mill's blog post "Drawing Presentable Trees" presents the algorithm in a very readable manner:

     http://billmill.org/pymag-trees/

mbostock• 11 years ago

Yep! This linear-time algorithm described by Buchheim et al. is used by d3.layout.tree:

https://github.com/d3/d3-hierarchy/blob/master/src/tree.js

llimllib• 11 years ago

I hadn't looked at that in forever! Glad somebody found it useful :)

The layout is awful, so I just now limited the page width and centered the body, which should make it a bit more readable.

peterhadlaw• 11 years ago

This is my Algorithms professor at IIT! :)

channon• 11 years ago

https://iit.edu/news/iittoday/?p=47371

lemming• 11 years ago

I love the fact that old papers often contain the complete source code to an implementation of the algorithm they're discussing.

cm21872• 11 years ago

Does anyone know a good algorithm for drawing a genealogy tree? I tried playing with this problem and it is quite hard to find something that looks OK. The problem is that it is a tree that has branches going both way (up and down).

rch2• 11 years ago

How well does graphviz handle your trees?

vidarh2• 11 years ago

Here's an example of part of my family tree with Graphviz [1] (using dot layout), and here's one with all my known ancestors [2] (using neato). A reasonably small subset works ok with dot (e.g. note that the first example excludes all siblings for example).

[1] http://hokstad.com/family-tree-using-graphviz-and-ruby

[2] http://hokstad.com/all-my-known-ancestors

austinjp2• 11 years ago

I would be very interested in solutions to this. It strikes me that genealogy trees are multi-dimensional, and compressing them to two dimensions makes layout far less optimal.

cm21872• 11 years ago

Plus there are lots of constraints. People of the same generation have to appear on the same vertical level. And there are lots of configurations that are simply impossible to represent. For instance a couple with three kids, each of them marries someone, how do we represent the parents of who they marry without crossing lines? Or it is relatively easy to represent someone having children from two different wives but how about three different wives without crossing lines?

And then it needs to look reasonably compact to be visually helpful. So it's a kind of a best effort basis.

xtrm1• 11 years ago

If you look closely enough, John S Tilford is effing Hackerman!!! OMG he did hack time

Tidier Drawings of Trees [pdf]

Related Stories