Graph Theory « Antimatroid, The

Posts Tagged ‘Graph Theory’

Radial tree drawing

Although not as interesting as a sunburst diagram, the radial tree view can hold its color against a number of more primitive information visualizations. A radial tree view places the root at the center of the screen then fans out each child node. Each child node then fans out its children within a restricted span and continues on until each leaf is reached. The strengths of the technique allow for any easy to digest depiction of the structure behind the data in a compact space. A common application is visualizing computer networks. It is worthwhile to examine the algorithm behind the technique because it is an exercise in identifying simplicity.

While in college, I would have approached this problem by trying to identify the location of nodes in terms of $(r, \theta)$ after all, I want a radial tree view- makes sense to sprint out the gate with a polar system right? While possible, this is a bad path to head down, as you end up drowning in a sea of extraneous details. Rather, it is better to think in terms of $(x,y)$ and then map to $(r, \theta)$ . To clarify that position, let’s think about how we’d go about drawing the run of the mill tree view as in the figure below:

radialtree_normal

First some observations:

Every node at a given depth lies on the same line.
Every child at a given depth is given an equal share of horizontal space independent of necessity relative to the space owned by its parent.

We can construct a simple recursive definition for drawing the tree if we think about these two facts. Given a node, we want to center the node at the top of a region then carve up a region into the number of child nodes where each sub region is equally wide and the same height as the parent minus a layering distance, then draw a line from the parent node to the child node. Continue doing so until all of the nodes have been drawn. All that remains is mapping this tree to the radial tree view below:

radialtree1

To achieve this last step, we want to map each node at $(x,y)$ to a point $\hat{C} + r \cdot(cos(\theta), sin(\theta))$ Where $\hat{C}$ is the center of the display area. The radius is simply the node’s present $y$ coordinate. $\theta$ can be determined as the ratio between the node’s present $x$ coordinate and the display width times $2 \pi$ . And thus, the mapping is complete.