Representation of graphs

Given a formulation of a problem, a compact representation is required both for theoretical purposes - measuring the complexity of algorithms, and for practical purposes - data compression. The adjacency lists method for representing graphs is compared to the information theoretic lower bounds, and it is shown to be optimal in many instances. For n-vertex labeled planar graphs the adjacency lists method requires 3 nlog n + O(n) bits, a linear algorithm is presented to obtain a 3/2 nlog n + O(n) representation while nlog n + O(n) is shown to be the minimum. © 1982 Springer-Verlag.