Tidier Drawings of Trees [pdf] | Hacker News Reader

Tidier Drawings of Trees [pdf]

emr.cs.iit.edu

31 points_virtu18 comments

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/

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

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.

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.

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

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

How well does graphviz handle your trees?

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

I see what you mean.

Try grouping siblings into subgraphs, and adjusting the length of edges between generations to approximate shells.

You might try NetworkX as well. I don't think it offers a better layout engine for you, but it supports graphviz and is awfully convenient for working with the graph itself.

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.

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.

Here's a good one: http://www.dgp.toronto.edu/~mjmcguff/research/#mcguffin_info...

It combines a tree of decendents from one person with a tree of ancestors of another person, to make a "dual-tree" with two foci. It preserves the property of people of the same generating being on the same level.

> 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?

The dual-tree approach wouldn't be able to show all of this at once, but with some affordances for navigating the tree (see the video) and indicators for where there are more nodes not shown, it should be reasonable to follow the relationships.

Also here's another interesting approach, using a radial tree with time information. I found this while trying to find the other paper: http://vis.berkeley.edu/courses/cs294-10-sp10/wiki/images/f/...

This is excellent, many thanks. Personally I'd got to McGuffin's fig 4 on the back of an envelope. Glad to find someone has taken things further.

I'm planning on drawing an extensive family tree, it's surprising how much physical space they take up.

You soon enough also have situations where a person belongs to two different generations, as well.

Title should contain (1981).

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

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

This is my Algorithms professor at IIT! :)

Reply on news.ycombinator.com