#
Space-efficient Static Trees and Graphs

##
Gio Borje

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)