Graph Layout
A graph is a set {V,E}, where V is a set of m vertices (nodes) and E is a set of n edges that link (associate) pairs of vertices to each other. A graph may be embedded in a space, in which case the set V is associated with a set of m points, one for each vertex, and the set E is represented by lines connecting points, one line for each edge.
The Edges applet in this series illustrates methods for calculating certain types of graphs on points in a space. We begin with the coordinates of the points, and compute different sets of edges from them. In this applet, we begin with a set of edges and compute a set of coordinates from them. Our input data consist of nothing more than a list of strings that are organized in pairs of node names denoting each edge.
The Random method embeds a set of random points in the plane, one for each node, and connects every pair of nodes in the input edge list with lines. Before drawing, we permute the node labels on the points to try to reduce crossings of lines. You can press the Random button repeatedly to see that the Random algorithm does a pretty good job of avoiding crossings.
The circle method spaces nodes evenly on the edge of a circle and then permutes labels to reduce crossings. This is a simple method that offers more regularity than Random.
The Digraph method assumes the edge list describes a directed graph (every pair in the edge list is taken to be directional, or from-to). It orders nodes in a hierarchy from top to bottom, such that every node at the bottom is a sink (all edges attached to it are incoming). Digraphs may have cycles, but this example does not. It is a tree.
The Network method arranges nodes on the plane so that nodes near each other in graph-theoretic distance (number of edges on the path connecting them) are near each other in Euclidean distance on the plane. The algorithm to do this is related to multidimensional scaling; you can see the slight delay while it iterates to a solution. Although this example is small, I have programmed it to work with hundreds of nodes and thousands of edges in reasonable time. Battista et al. (Graph Drawing: Algorithms for the Visualization of Graphs, Prentice-Hall, 1999) discuss some of these methods further.
The example used in this applet is derived from real data on a small Web site. The central node (in the Network view) is the home page. An nViZn application based on these methods provides a number of analytics for mining a Web site.