Embeddings and Contexts for Link Graphs

Graph-rewriting has been a growing discipline for over three decades. It grew out of the study of graph grammars, in which – analogously to string and tree grammars – a principal interest was to describe the families of graphs that could be generated from a given set of productions. A fundamental contribution was, of course, the double-pushout construction of Ehrig and his colleagues [4]; it made precise how the left-hand side of a production, or rewriting rule, could be found to occur in a host graph, and how it should then be replaced by the right-hand side. This break-through led to many theoretical developments and many applications. It relies firmly upon the treatment of graphs as objects in a category whose arrows are embedding maps.