Graph: White on Black

GD 2003 Graph Contest Description

Graph: White on Black


Submission (Postscript)

Poster (A4 -- .pdf)

Poster (A2 -- .pdf)

Animation (Large)

Animation (Small)

Image Gallery


The data for this graph was provided by Patrick Kenis of the Netherlands' Tilburg University. It is a real world example of a small social network that exists within an administration. The nodes in the graph represent organizations involved in drug policy making, and the edges are the informal lines of communication between the members of the different organizations. There are two types of communication between organizations, due to the nature of the data. One type is a confirmed line of communication (and is thus deemed important), whereas the other is an unimportant, unconfirmed relation. In our graph drawing, these types are differentiated by the coloring of edges, where green represents an important relation, while unimportant relations are represented by red edges.

The theme of the contest is graphs within graphs and we tried to highlight the inherent structure. In order to spatially distribute the graph sufficiently to prevent edge crossings, while maintaining the integrity of the graph data and presenting an aesthetically pleasing drawing, we chose to render the graph in a three dimensions. This spacial distribution served also to highlight the three, distinct subnetworks, which we emphasized by constructing our drawing in an animation. Drawn as “green” subgraphs, we used the “important” relations as a framework around which to build the remainder of the graph. Unimportant relationships within each subgraph were placed so as to be contained within the space occupied by the subgraph. By contrast, connections between the distinct subnetworks were placed exterior to these clusters, thus creating a cohesive drawing centered around and highlighting the important subgraphs. Finally, the remaining edges were placed in such a way as to facilitate ease of visual representation, without concealing the original subgraphs, while the solitary, unconnected vertex was placed at the origin, serving as a visual contrast to the density of the surrounding connections.

Our layout allows clear visualization of the connections both within and between the subnetworks. The use of three dimensions in our drawing allowed us to display the subgraphs in such a way as to emphasize the important relations as a framework within which the important ones could be intertwined. Two animations were created in order to more effectively display the three-dimensional nature of our drawing. A stereogram of the drawing was also produced which permits a simplified three-dimensional exposure. The GLuskap software package, developed at the University of Lethbridge, was a key tool for producing the necessary images.

Labyrinth: Computational Geometry at the University of Lethbridge

This page best viewed with: IE5+, Netscape 6+, or Mozilla
Copyright © 2003