Graph Structures
John L. Pfaltz · Journal of the ACM · 1972
The concept of a graph structure So in which a tree-like assemblage of subgraphs is used to represent a directed graph G is developed.This is directly analogous to the representation of lists by list structures.It is shown that with suitable restrictions, given So , G can be uniquely determined, and conversely, given G, So can be effectively constructed.A computer implementation which minimizes storage to represent G is presented, together with algorithms that illustrate the utility of graph structures, in particular, one that efficiently determines the existence of paths in G.