Space-efficient static trees and graphs
G. Jacobson · 1989
Data structures that represent static unlabeled trees and planar graphs are developed. The structures are more space efficient than conventional pointer-based representations, but (to within a constant factor) they are just as time efficient for traversal operations. For trees, the data structures described are asymptotically optimal: there is no other structure that encodes n-node trees with fewer bits per node, as N grows without bound. For planar graphs (and for all graphs of bounded page number), the data structure described uses linear space: it is within a constant factor of the most succinct representation.>