Succinct encoding of arbitrary graphs

We consider the problem of encoding graphs with n vertices and m   edges compactly supporting adjacency, neighborhood and degree queries in constant time in the Θ(logn)-bit word RAM model. The adjacency query asks whether there is an edge between two vertices, the neighborhood query reports the neighbors of a given vertex in constant time per neighbor, and the degree query reports the number of incident edges to a given vertex.We study the problem in the context of succinctness, where the goal is to achieve the optimal space requirement as a function of n and m  , to within lower order terms. We prove a lower bound in the cell probe model indicating it is impossible to achieve the information-theory lower bound up to lower order terms unless the graph is either too sparse (namely, m=o(nδ)m=o(nδ) for any constant δ>0δ>0) or too dense (namely m=ω(n2−δ)m=ω(n2−δ) for any constant δ>0δ>0).Furthermore, we present a succinct encoding of graphs supporting aforementioned queries in constant time. The space requirement of the encoding is within a multiplicative 1+ϵ1+ϵ factor of the information-theory lower bound for any arbitrarily small constant ϵ>0ϵ>0. This is the best achievable space bound according to our lower bound where it applies. The space requirement of the representation achieves the information-theory lower bound tightly within lower order terms where the graph is very sparse (m=o(nδ)m=o(nδ) for any constant δ>0δ>0), or very dense (m>n2/lg1−δn for an arbitrarily small constant δ>0δ>0).