Algorithm to computer the optimal layout of n-ary tree?

Question

I am looking for an algorithm that will automatically arrange all the nodes in an n-tree so that no nodes overlap, and not too much space is wasted. The user will be able to add nodes at runtime and the tree must auto arrange itself. Also note it is possible that the tree's could get fairly large ( a few thousand nodes ).

The algorithm has to work in real time, meaning the user cannot notice any pausing.

I have tried Google but I haven't found any substantial resources, any help is appreciated!

Answer 1

I took a look at this problem a while back and decided ultimately to change my goals from a Directed acyclic graph (DAG) to a general graph only due to complexities of what I encountered.

That being said, have you looked at the Sugiyama algorithm for graph layout?

If you're not looking to roll your own, I came across yFiles that did the job quite nicely (a bit on the pricy side though, so I did end up doing exactly that - rolling my own).