Representing Graphs by Knuth Trees
John L. Pfaltz · Journal of the ACM · 1975
ASSrRACT.By means of the :Knuth transform, arbitrary rooted trees may be represented compactly as binary trees.In this paper it is shown that the domain of this transform may be extended to a much wider class of graphs, while still maintaining its fundamental properties.Graphs, G, belonging to this extended domain are characterized first in terms of properties of an induced graph, G*, and then in terms of local properties of G itself.A classic kind of "forbidden" subgraph theorem characterizes nonrepresentable graphs.Finally, it is shown that any directed graph can be modified to make it representable under the transform.