Graphics Reference
In-Depth Information
Spanning Trees
5.3.2
It makes sense that we might be able to lay out a spanning tree nicely if we approxi-
mate graph-theoretic distance with Euclidean distance. his should tend to place ad-
jacent vertices (parents and children) close together and push vertices separated by
many edges far apart. he most popular algorithm for doing this is a variant of mul-
tidimensional scaling called the springs algorithm. It uses a physical analogy (springs
under tension represent edges) to derive a loss function representing total energy in
the system (similar to MDS stress). Iterations employ steepest descent to reduce that
energy.
Laying out a Simple Tree
Figure . (Wilkinson ) shows an example using data from a small website.
Each node is a page and the branches represent the links between pages; their thick-
ness represents tra c between pages (this website has no cross-links). It happens
that the root is located near the center of the display. his is a consequence of the
force-directed algorithm. Adjacent nodes are attracted and nonadjacent nodes are
repelled.
he springs algorithm brings to mind a simple model of a plant growing on a sur-
face. his model assumes branches should have a short length so as to maximize
Figure . . Force-directed layout of a website tree
Search WWH ::




Custom Search