Ian Kash

Graphs used in applications such as meshing and modeling the web can be massive. It is useful to be able to represent them succinctly while supporting efficient queries. We have theory about data structures for representing graphs with good separators in linear space with constant time adjacency queries and neighbor queries in time proportional to the number of neighbors. We have an implementation of this theory using edge separators, which uses at most 11 bits per edge on graphs we tested. We also have some preliminary results that indicate we can achieve reasonably fast queries.