Huy's Notes
Tree Drawing Algorithm

Tree Drawing Algorithm

#algorithm #graphics #wip

Read:

  • Tidy Drawings of Trees
  • Tree Drawing Algorithms

Notes:

  • Tree drawing is an interesting and very complex task on the computer and there are many techniques, algorithms to do it.
  • To draw a tree diagram, it's pretty simple, we first need to positioning all the nodes and then, connect them all.
  • But positioning itself is a very complex problem, since it bounds to many other constraints, one of them is the physical limit of the drawing surface (screen size,...).
  • Another problem is, nodes usually being labelled, and the positioning algorithm must also consider these label to make sure they're not overlaped, and the edges must avoid nodes.
  • Aesthetics are important properties of every diagram, some main properties are:
    • Area: the algorithm must be able to draw as many nodes as possible on a limited area.
    • Aspect Ratio: the ratio between width and height of the whole diagram, of course. The optimal aspect ratio would be 1. That mean, the diagram should not be too wide or too tall but balanced.
    • Subtree Separation: any two node-disjoint subtrees should have their bounding rectangle not overlap with each other.
    • Distance between root and leaves: it might be related to area and other properties.

(To be continued)

Referred in


If you think this note resonated, be it positive or negative, please feel free to send me an email and we can talk.