Addressable data graphs

This paper continues the study of the classes of data graphs which are implementable in a random access memory using "relative addressing" and "relocatable realization", which was initiated in [i]. A new characterization of the class of rooted (=relative addressable) data graphs yields simple and natural proofs of the preservation of rootedness under broad families of operations for composing data graphs. These positive results somewhat diminish the impact of the general unsolvability of detecting rootedness and free-rootedness { =relocatability) in data graphs.