An edge grammar is a formal mechanism for representing families of rel
ated graphs (binary trees, hypercubes, meshes, etc.). Given an edge gr
ammar, larger graphs in the family are derived from simple basis graph
s using edge rewriting rules. A drawback to many graph grammars is tha
t 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 i
llustrate edge grammars and analyze them in the context of formal lang
uage theory. Our results include hierarchy and decidability properties
. Because this work originally was motivated by a need to represent gr
aph families found in parallel computation, the application of edge gr
ammars in this context is also discussed.