Minimal storage representations for binary relations (Q789170)

The problem considered is storing a binary relation in a sequential storage space where memory locations are accessible via pointers (from other locations) and sequential movement. The goal is to bound the amount of storage required to represent a binary relation over a set S of n elements. The approach is to represent the storage problem as a graph embedding problem. The relation is represented as a bipartite directed graph over two copies of S. The storage space is represented as a directed graph with maximum out-degree 2, called a storage graph. Presumably, the vertices in the storage graph are memory locations, and the two edges from each vertex reference the location pointed to and the next location in sequence. However, the authors do not say how a cycle among the ''next location'' edges can be interpreted. The main results say that every graph of n vertices can be embedded in a storage graph of size (number of vertices \(+\) number of edges) at most \(144(n^ 2/\log n)\), while some graph of n vertices requires a graph of size at least \(1/7(n^ 2/\log n)\) to embed it. The lower bound's significance for the binary relation problem is questionable. The proof is not constructive, so it is possible that no bipartite graph of n vertices requires a storage graph as large as \(1/7(n^ 2/\log n)\).