Graphics Reference
In-Depth Information
root node, which has one or more children and no parent. Examples of hierarchical
trees are those produced by decision-tree and hierarchical clustering algorithms.
A spanning tree is an undirected geometric tree. Spanning trees have n
−
edges
that define all distances between n nodes.hisisarestrictionofthen
edges
in a complete graph. A minimum spanning tree (MST) has the shortest total edge
length of all possible spanning trees.
(
n
−
)
Ultrametric Trees
Ifthenode-to-leafdistancesaremonotonicallynondecreasing(i.e.,noparentiscloser
to the leaves than its children are), then a hierarchical tree is ultrametric.Anultra-
metric is a metric with a strong form of the triangle inequality, namely,
d
(
x, y
)
max
[
d
(
x, z
)
, d
(
y, z
)]
.
In an ultrametric tree, the graph-theoretic distances take at most n
possible val-
ues, where n is the number of leaves. his is because of the ultrametric three-point
condition, which says we can rename any x, y, z such that
−
d
(
x, y
)
d
(
x, z
)=
d
(
y, z
)
.
Another way to see this is to note that the distance between any two leaves is deter-
mined by the distance of either to the common ancestor.
Additive Trees
Let D be a symmetric n by n matrix ofdistances d
ij
.LetT be a hierarchical tree with
oneleafforeachrow/columnof D. T isanadditivetreefor D if,foreverypairofleaves
(
, the graph theoretic distance between the leaves is equal to d
ij
. Additive trees
rest on a weaker form of the triangle inequality than do ultrametric trees. namely,
t
i
, t
j
)
d
(
x, y
)[
d
(
x, z
)+
d
(
y, z
)]
.
Graph Drawing
5.3
Agraphisembeddable on a surface if it can be drawn on that surface so that edges
meetonly atvertices. Agraphis planar if itisembeddable onasphere(and,byimpli-
cation, the unbounded plane). We can use a theorem by Euler to prove a particular
graph is not planar, but we can prove a particular graph is planar only by drawing it
without edge crossings. Drawinggraphs is morethan atheoretical exercise, however.
Findingcompactplanardrawingsofgraphs representing electrical circuits,forex-
ample, is a critical application in the semiconductor industry. Other applications in-
volve metabolic pathways, kinetic models, and communications and transportation
networks. Spherical applications involve mapping the physical nodes of the Internet
and world trade routes.
