Linear and Context-Free Graph Grammars

Abstract

Topological characterizations of sets of graphs which can be generated by contextfree or linear grammars are given. It is shown, for example, that the set of all planar graphs cannot be generated by a context-free grammar while the set of all outerplanar graphs can