Home

There are really two important pieces of information in a tree. One is the hierarchical nature of the tree: the parent-child relationships. The other is a relative “distance” between the nodes. Children and their parents should be close, but leaf nodes in totally different branches of the tree should be very far apart (probably somehow proportional to the number of links).  Let’s imagine putting this into a Euclidean (say 2D) space. First, we would probably put the root at the origin. Then, place the first level equidistant around it. Then place the second level equidistant from all those points. Eventually we will run out of space. The hierarchical links are sort of represented (distances between child/parent are maintained), but importantly, the distances between siblings gets smaller. That is, we don’t have enough “space”. One way around, might be to increase dimensions but then you’d need to increase those with the number of levels you have, which brings a whole host of other problems. Long story short, Euclidean space isn’t a good representation for tree-like graph data.  So what is?