Figure 1. Example graphs

This is the story of an unexpected discovery along the way.

Although there are several visualization programs floating around the Web, none did exactly what I wanted at a price I could afford. After some research, I decided to write my own system using a force-directed layout algorithm.

The method, based on a physical simulation, models nodes as charged particles and edges as springs. Initially, the nodes are plopped down randomly in a plane, and the program computes the force vectors that result as the particles push each other apart while the springs pull them together. Each node's position updates accordingly. The process repeats until the system reaches equilibrium. While it can take thousands of iterations to draw even a simple graph, the method is simple to code and works surprisingly well in a variety of circumstances.

Once I'd completed the prototype, I was ready to generate lots of samples. Since combing Introduction to Algorithms for sample graphs was truly painstaking, I hit upon a more automated approach: using the letters in a word as nodes and the relationship between letters as edges. For example, the word "david" can be converted into a graph with four nodes ("d", "a", "v", and "i") and four edges ("d-a", "a-v", "v-i", and "i-d"). The following table shows "david" encoded as an XML input file to the program and the program's resulting output.

<?xml version="1.0" ?>
<GRAPH ID="david">
  <NODES>
    <NODE ID="d" />
    <NODE ID="a" />
    <NODE ID="v" />
    <NODE ID="i" />
  </NODES>
  <EDGES>
    <EDGE EDGE_START="d" EDGE_END="a" />
    <EDGE EDGE_START="a" EDGE_END="v" />
    <EDGE EDGE_START="v" EDGE_END="i" />
    <EDGE EDGE_START="i" EDGE_END="d" />
  </EDGES>
</GRAPH>

This approach has several advantages. First, and most obvious, there are lots and lots of words; you can download free "word lists" with thousands of entries, so finding test data is a breeze. Second, words are easy to convert into graphs — it took all of 10 minutes to write a program to encode a word into the XML-format shown in the example. Third, words have many different structures, so they produce a variety of shapes. Finally, and most important, it's easy to verify that the program works correctly since there is always a route through the nodes that spells the original word. (In the example above, we can find "david" by starting at "d" and working our way counterclockwise.)

Here are a few representative examples of the diversity of shapes found in just six words. Assuming you can use the same letter multiple times, notice how you can always find a route through the edges to spell the original word.

At this point the law of unintended consequences took over. While I had planned to build a sophisticated data analysis tool by merging ideas from physics and graph theory, everyone who saw the test cases were so intrigued that the conversation usually never got past "Cool — 'utilitarian' looks like a rocket from the 50s!" or (from a chemist friend) "Ohhh, that one looks like Benzene!"