CS 269S, Fall 2012: Theory Seminar
Bren Hall, Room 1423, 1pm
October 12, 2012:

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)