Implicit graph

[1] This type of implicit graph representation is analogous to an adjacency list, in that it provides easy access to the neighbors of each vertex.

PPAD is an analogous class defined on implicit directed graphs that has attracted attention in algorithmic game theory because it contains the problem of computing a Nash equilibrium.

[3] The problem of testing reachability of one vertex to another in an implicit graph may also be used to characterize space-bounded nondeterministic complexity classes including NL (the class of problems that may be characterized by reachability in implicit directed graphs whose vertices are O(log n)-bit bitstrings), SL (the analogous class for undirected graphs), and PSPACE (the class of problems that may be characterized by reachability in implicit graphs with polynomial-length bitstrings).

For instance, Childs et al. used neighborhood representations of implicit graphs to define a graph traversal problem that can be solved in polynomial time on a quantum computer but that requires exponential time to solve on any classical computer.

[6] In the context of efficient representations of graphs, J. H. Muller defined a local structure or adjacency labeling scheme for a graph G in a given family F of graphs to be an assignment of an O(log n)-bit identifier to each vertex of G, together with an algorithm (that may depend on F but is independent of the individual graph G) that takes as input two vertex identifiers and determines whether or not they are the endpoints of an edge in G. That is, this type of implicit representation is analogous to an adjacency matrix: it is straightforward to check whether two vertices are adjacent but finding the neighbors of any vertex may involve looping through all vertices and testing which ones are neighbors.

For some families, a simple counting argument proves that adjacency labeling schemes do not exist: only O(n log n) bits may be used to represent an entire graph, so a representation of this type can only exist when the number of n-vertex graphs in the given family F is at most 2O(n log n).

[7][10] Kannan et al. asked whether having a forbidden subgraph characterization and having at most 2O(n log n) n-vertex graphs are together enough to guarantee the existence of an adjacency labeling scheme; this question, which Spinrad restated as a conjecture, remains open.

Rivest and Vuillemin proved that any deterministic algorithm for any nontrivial graph property must test a quadratic number of pairs of vertices.