Representing graphs implicitly using almost optimal space

How to represent a graph in memory is a fundamental data-structuring proble m. In the usual representations, a graph is stored by representing explicit ly all vertices and all edges. The names (labels) assigned to vertices are used only to encode the edges and reveal nothing about the structure of the graph itself and hence are a "waste" of space. In this context, we present a general framework for labeling any graph so that adjacency between any t wo given vertices can be tested in constant time. The labeling scheme assig ns to each vertex x a O(delta (x) log(2) n) bit label, where n is the numbe r of vertices and delta (x) is x's degree. The adjacency test can be perfor med in seven steps and the scheme can be computed in polynomial time. The p roposed graph encoding positively demonstrates its superiority over the usu al representations, i.e. adjacency matrix and adjacency list representation s, which require O(n log n) bit label per vertex and constant time adjacenc y test, and O(delta (x)log n) bit label per vertex and O(log delta (x)) ste ps to test adjacency, respectively. Additionally, the labeling scheme is im plicit, that is: no pointers are used. (C) 2001 Elsevier Science B.V. All r ights reserved.