Abstract
In this paper we associate with each graph g of a very large class of graphs a set of formal languages. Each such language can serve as description of g in the sense that g can be reconstructed from it in a unique manner.
Our approach permits the convenient representation of finite and infinite graphs both for human communication and for storing or processing graphs in a computer. Since the model only requires that nodes of the graph are labeled “locally unique”, the relabeling of nodes necessary for performing certain operations on graphs using their descriptions is kept to a minimum. The model further allows a nice classification of graphs based on results on formal languages and provides means to define sequences of graphs as requiredin applications such as developmental biology.
†This paper was written while the first author was visiting the University of Karlsruhe and was partially supported by the National Research Council of Canada, Grant No. A7403.
†This paper was written while the first author was visiting the University of Karlsruhe and was partially supported by the National Research Council of Canada, Grant No. A7403.
Notes
†This paper was written while the first author was visiting the University of Karlsruhe and was partially supported by the National Research Council of Canada, Grant No. A7403.