4.11 Graph Properties Conserved by Rules

Many rules (at least when they exhibit complex behavior) seem to lead to statistically similar behavior, independent of their initial conditions. But there could still be disjoint families of states that can be reached from different initial conditions, perhaps characterized by different graph or hypergraph invariants.

As one example, we can ask whether there are rules that preserve the planarity of graphs. All rules with signature 1₂  2₂ inevitably do this. A rule like

might not at first appear to:

But a different graph layout shows that actually all these graphs are planar [36]:

Among larger rules, many still preserve planarity. But for example, {{x,y},{x,z}}{{x,z},{x,w},{y,w},{z,w}} does not, since it transforms the planar graph

to the nonplanar one:

In general, a graph is planar so long as it does not contain as a subgraph either of [37]

so a rule preserves planarity if (and only if) it never generates either of these subgraphs.

Planarity is one of a class of properties of graphs that are preserved under deletion of vertices and edges, and contraction of edges. Another such property is whether a graph can be drawn without crossings on a 2D surface of any specific genus g [38]. It turns out [38] that for any such property it is known that there are in principle only a finite number of subgraphs that can “obstruct” the property—so if a rule never generates any of these, it must preserve the property.