Collaborators: Eric Schweikardt, Nwanua Elumeze, Mike Eisenberg
Graph theory is an important branch of modern mathematics that is used throughout the physical, social, and artificial sciences. For example, it is used in electrical engineering to model circuits, in computer science to understand the properties of data structures and algorithms that operate on them, and in anthropology, to represent family structures in a society. The elements of graph theory are simple and easily grasped by a child of twelve, yet its theorems and applications are profound and important. Yet we do not teach graph theory in our schools, and despite its relative accessibility graph theory remains largely the domain of experts. This need not be so.
Graphmaster is a computationally enhanced construction kit designed to elucidate the fundamentals of graph theory and to provide a platform for experimenting with graphs. One can experiment with graphs using only paper and pencil, and games such as Sprouts, or puzzles like the Königsberg bridge problem are often used to introduce graph theory to beginners. A computationally enhanced construction kit offers a tactile, and tangible way to interact with graph theory concepts and it can augment the experience available with paper and pencil.
The kit has two kinds of parts: nodes and edges. Physically, nodes are small plastic spheres with embedded ports where edges can connect. Edges are short lengths of electro-luminescent wire with connectors at their ends that snap magnetically into the nodes. Each edge can light up in blue or green, and it can sense when it is being touched. When an edge is connected between two nodes, microcontrollers in each node detect the new link so that Graphmaster “knows” about the connection. Depending on the program that Graphmaster is running (actually, the program runs in a distributed fashion in each of the nodes), the kit behaves differently.
For example, a basic Graphmaster program would detect cycles in the graph. When one connects a set of nodes with links to form a cycle, Graphmaster would light up the cycle. Or Graphmaster could quietly detect the cycles without displaying them, and when an edge is touched it could light up all the cycles that contain that edge. Or Graphmaster could be programmed to identify and display tightly coupled clusters in a graph. Games like Sprouts, or simulations of the Königsberg bridge problem could also be built by a programmer using Graphmaster’s simple programming language.
Graphmaster programs are written on a personal computer and loaded into the microcontrollers in all the nodes. The microcontrollers then execute the program autonomously and communicate through wires embedded in the links.
2009 A Tangible Construction Kit for Exploring Graph Theory, Schweikardt, E., Elumeze, N., Eisenberg, M., Gross, M. , ACM Tangible and Embedded Interaction (TEI), Cambridge UK, Feb 16-19. 373-376. [pdf]