Representing graph families with edge grammars

An edge grammar is a formal mechanism for representing families of related graphs (binary trees, hypercubes, meshes, etc.). Given an edge grammar, larger graphs in the family are derived from simple basis graphs using edge rewriting rules. A drawback to many graph grammars is that they cannot represent some important, highly regular graph families such as the family of shuffle-exchange graphs. Edge grammars, however, exist for all "computable" graph families, and simple edge grammars exist for most regular graph families. In this paper, we define and illustrate edge grammars and analyze them in the context of formal language theory. Our results include hierarchy and decidability properties. Because this work originally was motivated by a need to represent graph families found in parallel computation, the application of edge grammars in this context is also discussed.