On Succinct Representation of Graphs

In the first part, we present a space lower bound on how compact a representation of a graph can be, if we require performing adjacency and neighborhood queries in constant time. In the second part, we see a matching upper bound by describing a graph representation that supports the aforementioned queries in constant time. Moreover, we explore briefly the topic of succinct representation of special classes of graphs.