Cellular Automata on Trivalent Networks
This Demonstration shows the evolution of cellular automata on trivalent networks (cubic graphs). Each node evolves according to its own color and the colors of its three neighbors (without regard to any "ordering" of its neighbors.) The transformation rule is shown in the top of each graphic, with the inner color in the center circle representing the new color for the node. The bottom left panel shows the connectivity structure of the network and the state of the system at any given point in time. The bottom right panel shows the evolution of the system over time from top to bottom (just as in a conventional one dimensional cellular automaton diagram) but with the nodes ordered from left to right as set forth at the top of the panel. This ordering corresponds to the top to bottom ordering of a "layered digraph" embedding of the network. To evolve the system, simply drag the frame slider to the right. You can control the particular cubic graph topology, the cellular automaton rule used to evolve the system, and the initial configuration of the system.
The code underlying this Demonstration shows how the methods used here can be readily adapted to address cellular automata on arbitrary regular graphs with greater numbers of colors.