A fundamental operation on representations of graphs is the adjacency query: given two nodes u and v, tell whether or not the edge (u,v) is present in the graph.

Two standard textbook representations of graphs are adjacency matrices and adjacency lists. The first answers adjacency queries in O(1) time, but uses n^2 bits space, which is superlinear for sparse graphs. The latter uses linear space, but adjacency queries now involve searching adjacency lists, which may have length n.

The challenge therefore is to find representations which are both fast and compact, i.e., support adjacency queries in O(1) time and use linear size.

Quite a number of such representations have been developed, but so far only for static graphs. In this talk, we study the dynamic version of the problem and give a representation which also allows insertions and deletions of edges in O(1) and O(log n) amortized time per update, respectively.

The representation is a slight variation of the adjacency list representation, equipped with a very simple, almost canonical update algorithm. For the complexity analysis, we first show that despite its simplicity, the algorithm achieves a constant competitive ratio against the optimal off-line way of maintaining such adjacency lists during a sequence of updates, and then provide an upper bound on this optimal off-line solution.

Our representation works for graphs which are uniformly sparse, i.e., where all subgraphs also are sparse. Many well-known classes of sparse graphs have this property, e.g., planar graphs, graphs of bounded treewidth, and, more generally, graphs of bounded arboricity.

This is joint work with Gerth S. Brodal.

Host: Peter Kornerup