An Experimental Analysis of a Compact Graph Representation

In previous work we described a method for compactly representing graphs with small separators, which makes use of small separators, and presented preliminary ex-perimental results. In this paper we extend the experi-mental results in several ways, including extensions for dynamic insertion and deletion of edges, a comparison of a variety of coding schemes, and an implementation of two applications using the representation. The results show that the representation is quite ef-fective for a wide variety of real-world graphs, including graphs from finite-element meshes, circuits, street maps, router connectivity, and web links. In addition to signif-icantly reducing the memory requirements, our imple-mentation of the representation is faster than standard representations for queries. The byte codes we intro-duce lead to DFT times that are a factor of 2.5 faster than our previous results with gamma codes and a fac-tor of between 1 and 9 faster than adjacency lists, while using a factor of between 3 and 6 less space.