Uniform data encodings

Abstract

Given two finite, directed, edge-labeled graphs, G (the guest) and H (the host) an encoding of G into H is an injection of guest-graph edges into host-graph paths that induces an injection of G vertices into H vertices. An encoding is uniform if like-labeled edges map to like-labeled paths. Encodings and uniform encodings are motivated by data structure representation issues. Although uniform encodings are economically expressed, three types of analysis indicate diseconomies introduced by the uniformity condition. First, space usage (i.e., the size of the host as a function of the size of the guest) can be exponential for 'natural' encodings such as uniform encodings of arrays into trees. By contrast, strongly connected hosts of size equal to the guests are adequate for nonuniform encodings. Secondly, the edge dilation under uniform encodings can be nonpolynomial in the size of the guest. By contrast, the same graphs can be nonuniformly encoded with edges mapping to paths of unit length. Thirdly, finding uniform encodings, even when the guest is a line, is PSPACE-complete. By contrast, there is a linear time algorithm for nonuniform encoding of lines in graphs. Additional upper and lower bounds amplify the limitations of uniform data encodings. © 1980.