REPRESENTING GRAPH FAMILIES WITH EDGE GRAMMARS

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.