New data structures are developed that represent static unlabeled trees and planar graphs. These structures are more space-efficient than conventional pointer-based representations, but (to within a constant factor) they are just as timeefficient for traversal operations. For trees, the data structures described here 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 pagenumber), the data structure described uses linear space: it is within a constant factor of the most succinct representation.
(Based on a paper by Guy Jacobson)