2

Graph algebras and widths of graphs

We will define graph operations that generalize the concatenation of words. Some of these operations have been used in Section 1.1 to define the cographs and the series-parallel graphs. We will define actually two signatures of graph operations, hence two graph algebras. Both algebras will be defined in such a way that their equational sets are exactly the sets defined by certain context-free graph grammars. (The notion of an equational set has been presented informally in Section 1.1.4 and will be studied in detail in Chapter 3.)

Two main types of *context-free sets of graphs* defined by certain graph rewriting mechanisms have emerged from the intense research conducted from around 1980 and synthesized in ...

Start Free Trial

No credit card required