Title: Evaluating generally intractable graph properties on graphs generated by graph grammars
Abstract: It is known that many NP-hard graph properties could be evaluated efficiently on graphs having sparse or inductive structure (having bounded treewidth, bounded clique-width, etc.), using dynamic programming techniques.
We consider classes of graphs, generated by several types of graph grammars. The framework of NCE graph grammars is presented, and explicit bounds for treewith and clique-width of corresponding graph languages are computed.