On compact encoding of pagenumber k graphs
In this paper we show an information-theoretic lower bound of kn-o(kn) on the minimum number of bits to represent an unlabeled simple connected n-node graph of pagenumber k. This has to be compared with the efficient encoding scheme of Munro and Raman of 2kn + 2m + o(kn + m) bits (m the number of edges), that is 4kn + 2n + o(kn) bits in the worst-case. For m-edge graphs of pagenumber k (with multi-edges and loops), we propose a 2m log(2) k + O(m) bits encoding improving the best previous upper bound of Munro and Raman whenever m <= 1/2 kn / log(2) k. Actually our scheme applies to k-page embedding containing multi-edge and loops. Moreover, with an auxiliary table of o(m log k) bits, our coding supports (1) the computation of the degree of a node in constant time, (2) adjacency queries with O(log k) queries of type rank; select and match, that is in O (log k . min {log k / log log m; log log k }) time and (3) the access to delta neighbors in O(delta) runs of select; rank or match.
lower bound k-page embedding encoding of graphs