Graphics Reference
In-Depth Information
he graph-drawing (or graph-layout) problem is as follows. Given a planar graph,
how do we produce an embedding on the plane or sphere? And if a graph is not pla-
nar, how do we producea planar layout that minimizes edge crossings? hestandard
text on graph drawing is Di Battista et al. (
), which is a comprehensive bibliog-
raphy. Kruja et al. (
) give a history of the problem. See also the various years
of the Proceedings of the International Symposium on Graph Drawing,publishedby
Springer.
Different types of graphs require different algorithms for clean layouts. We begin
with trees. hen we discuss laying out networks and directed cyclic graphs. In most
examples, the basic input data are nonnumeric. hey consist of an unordered list of
vertices (node labels) and an unordered list of edges (pairs of node labels). If a graph
is connected, then we may receive only a list of edges. If we have a weighted graph,
the edge weights may be used in the loss function used to define the layout. We will
discuss other forms of input in specific sections.
Hierarchical Trees
5.3.1
Suppose we are given a recursive list of single parents and their children. In this list,
each child has one parent and each parent has one or more children. One node, the
root, has no parent. his tree is a directed graph because the edge relation is asym-
metric. We can encapsulate such a list in a node class:
Node{
Node parent;
NodeList children;
}
Perhaps the most common example of such a list is the directory structure of a hi-
erarchical file system. A display for such a list is called a tree browser.Creatingsuch
a display is easy. We simply walk the tree, beginning at the root, and indent children
in relation to their parents. Figure
.
shows an example that uses the most common
vertical layout. Figure
.
shows an example of a horizontal layout. Interestingly, the
“primitive” layout in Fig.
.
has been found to be quite effective when compared to
more exotic user-interface tree layouts (Kobsa
).
Supposenowwearegivenonlyalistofedgesandtoldtolayoutarootedtree.Tolay
outatreeusingonly anedgelist,weneedtoinventory theparent-child relationships.
First, we identify leaves by locating nodes appearing only once in the edge list. We
then assign a layer value to each node by finding the longest path to any leaf from
that node.henwebeginwith the leaves, group childrenbyparent, andalign parents
above the middle child in each group. Ater this sweep, we can move leaves up the
hierarchy to make shorter branches. Figure
.
shows an example using this layout
algorithm. he data are adapted from weblogs of a small website. he thicknesses of
thebranchesofthetreeareproportionaltothenumberofvisitorsnavigatingbetween
pages represented by nodes in the tree.
Ifthe nodes ofa tree areorderedbyan external variable suchasjoining orsplitting
distance, then we may locate them on a scale instead of using paternity to determine
ordering. Figure
.
shows an example of this type of layout using a cluster tree. he
