Edges of Graphs
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.
This applet illustrates several graphs that may be computed for a set of m data points embedded in a space. These are discussed in Chapter 8 of The Grammar of Graphics (Springer-Verlag, 1999). The Voronoi tessellation partitions a set of data points such that every point within a polygon is closer to the data point in that polygon than to any other data point in another polygon. The Delaunay triangulation connects each data point to data points in adjacent Voronoi polygons. If you toggle between Voronoi and Delaunay, you should see that the Voronoi edges are perpendicular to the Delaunay edges. The computation of Delaunay implies the computation of Voronoi.
The convex hull delineates the outer boundaries of a set of points. It is a subset of the edges in the Delaunay triangulation. The convex hull has two defining properties: 1) any straight line intersects edges of the hull a maximum of two times, and 2) no point is outside the hull.
The minimum spanning tree joins every member of a set of data points such that there are no cycles and the sum of the edge lengths is minimum. Any two nodes in a MST are connected by exactly one edge. The MST is a tree because it is connected (every pair of points has a path from one to another along the edges) and it is acyclic (no path visits a point twice).
The Tile button fills in all closed polygons with random colors. It does nothing for MST because edges of an acyclic graph cannot create closed polygons. Tiling 1000 points with Delaunay makes a random quilt.