A map is a representation of a graph on a surface. More generally, a hypermap is a representation of a hypergraph on a surface. These representations arise in various contexts in the theory of graphs and hypergraphs, and it is important therefore to develop a general approach to their generation. This paper presents a hypermap-generating system that is based on a purely combinatorial formulation of both the hypermaps and the grammars that generate them.

Hypermaps are defined in terms of darts, where each dart is a pair made up of a vertex identifier and a corresponding incident edge (a component of a hyperedge). Then a cyclic permutation &sgr; is defined that maps each vertex identifier into the next vertex identifier at the same vertex (each identifier specifies a single incidence of a hyperedge). Thus &sgr; describes each vertex in terms of the incidence of its hyperedges. A complementary cyclic permutation &agr; maps each vertex identifier into the next vertex identifier for the same hyperedge; thus &agr; describes each hyperedge in terms of its component vertices.

Based on this definition of a hypermap, the author describes a hypergraph rewriting model in terms of productions on labeled hypergraphs that derive new labeled hypergraphs in the form of combinatorial products. This model is based on the concept of a hypergraph grammar, and the derived classes of hypergraphs are called hypergraph languages. A special kind of hypergraph grammar, called an H-grammar, is then introduced and used to explore the structure of hypergraph languages. Finally, some decidability theorems for hypergraph grammars and H-grammars are stated and proved.

The paper is based on the author’s doctoral dissertation at the University of Bordeaux. It is generally well written and presents new results. The material is theoretical, however, and will be accessible only to readers with a substantial knowledge of hypergraphs and formal language theory.