Succinct Representation of Trees and Graphs

I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners. I understand that my thesis may be made electronically available to the public. ii In this thesis, we study succinct representations of trees and graphs. A succinct representa-tion of a combinatorial object is a space efficient representation that supports a reasonable set of operations and queries on the object in constant or near constant time on the RAM with logarithmic word size. The storage requirement of a succinct representation is intended to be optimal to within lower order terms. We first propose a uniform approach for succinct representation of various families of trees. The method is based on two recursive decompositions of trees into subtrees. The approach simplifies the existing representation of ordinal trees while allowing the full set of navigational operations and queries. The approach applied to cardinal (i.e., k-ary) trees yields a space-optimal succinct representation allowing cardinal-type operations (e.g., deter