Graphics Reference
In-Depth Information
Networks
5.3.3
Networks are, in general, cyclic graphs. Force-directed layout methods oten work
well on networks. here is nothing in the springs algorithm that requires a graph
to be a tree. As an example, Fig.
.
shows an associative network of animal names
from an experiment in Wilkinson (
). Subjects were asked to produce a list of
animal names.Namesfoundtobeadjacent insubjects' listswereconsidered adjacent
in a graph.
Directed Graphs
5.3.4
Directed graphs are usually arranged in a vertical (horizontal) partial ordering with
source node(s) at top (let) and sink node(s) at bottom (right). Nicely laying out a di-
rected graph requires a topological sort. Wetemporarily invert cyclical edges to con-
vert the graph to a directed acyclic graph (DAG) so that the paths-to-sink can be
identified. hen we do a topological sort to produce a linear ordering of the DAG
such that for each edge
,vertexu is above vertex v. Ater sorting, we iteratively
arrange vertices with tied sort order so as to minimize the number of edge cross-
ings.
Minimizing edge crossings between layers is NP-hard. We cannot always be sure
to solve the problem in polynomial time. It amounts to maximizing Kendall's τ cor-
relation between adjacent layers. Heuristic approaches include using direct search,
simulated annealing, or constrained optimization.
Figure
.
shows a graph encapsulating the evolution of the UNIX operating sys-
tem. It was computed by the AT&T system of graph layout programs.
(
u,v
)
Figure
.
.
Cyclic graph of animal names
