The simplest representations for graphs use adjacency matrices/lists, meaning that each node and edge is explicitly represented. The importance of implicit representations for graphs exhibiting strong regularities has long been recognized. For instance, Galperin & Wigderson (1983), Papadimitriou & Yannakakis (A Note on Succinct Representations of Graphs, 1986) explored the question of graphs whose adjacency matrix is represented by a Boolean formula answering whether or not (i,j) is an edge given the binary representation of the node numbers i and j. Under some commonly satisfied constraints on reductions, P-complete problems for explicit graphs become PSPACE-complete for this representation, NP-complete problems become NEXPTIME-complete, etc.
A natural approach to such regular graphs is to represent the Boolean formula using a ROBDD; the difficulty is that classical algorithms tend to enumerate nodes one by one, which incurs exponential cost on such a representation and thus is to be avoided. There have been papers published on classical problems being solved using such a representation, e.g. Gentilini et al. (Computing strongly connected components in a linear number of symbolic steps), Woelfel (Symbolic topological sorting with OBDDs).
I'm wondering whether there is some survey of such techniques, because it's inconvenient to dredge the literature in such of the state of the art...
