Succinct Representations of Arbitrary Graphs

We consider the problem of encoding a graph with

n

vertices and

m

edges compactly supporting adjacency, neighborhood and degree queries in constant time in the log

n

-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 that it is impossible to achieve the information-theory lower bound within lower order terms unless the graph is too sparse (namely

m

 = 

o

(

n

δ

) for any constant

δ

> 0) or too dense (namely

m

 = 

ω

(

n

2 − 

δ

) for any constant

δ

> 0).

Furthermore, we present a succinct encoding for graphs for all values of

n

,

m

supporting queries in constant time. The space requirement of the representation is always within a multiplicative 1 + 

ε

factor of the information-theory lower bound for any arbitrarily small constant

ε

> 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 when the graph is sparse (

m

 = 

o

(

n

δ

) for any constant

δ

> 0).