Data graphs and addressing schemes

A data graph is obtained from a data structure by masking out the specific data items at the nodes of the structure and concentrating only on the linkages in the structure. This factoring operation is done implicitly when one refers to "tree structures" or "arrays" as generic objects. Structural uniformities in data graphs can often be exploited to facilitate and systematize the accessing of nodes in the graph and the implementation of the graph in a computer. This paper presents a model for data graphs which can be used to study such uniformities. The main results reported algebraically characterize, in terms of structural uniformities, those classes of data graphs which can be implemented by "relative addressing" and by "relocatable realizations". © 1971 Academic Press, Inc.