Compact Representations of Separable Graphs

We consider the problem of representing graphs compactly while supporting queries efficiently. In particular we describe a data structure for representing n-vertex unlabeled graphs that satisfy an O(nc)-separator theorem, c < 1. The structure uses O(n) bits, and supports adjacency and degree queries in constant time, and neighbor listing in constant time per neighbor. This generalizes previous results for graphs with constant genus, such as planar graphs.We present experimental results using many "real world" graphs including 3-dimensional finite element meshes, link graphs of the web, internet router graphs, VLSI circuits, and street map graphs. Compared to adjacency lists, our approach reduces space usage by almost an order of magnitude, while supporting depth first traversal in about the same running time.