Representation of graphs

Summary 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 3nlogn + O(n) bits, a linear algorithm is presented to obtain a 3/2nlogn + O(n) representation while nlogn + O(n) is shown to be the minimum.