  We study the two-player communication problem of determining whether two
vertices $x, y$ are nearby in a graph $G$, with the goal of determining the
graph structures that allow the problem to be solved with a constant-cost
randomized protocol. Equivalently, we consider the problem of assigning
constant-size random labels (sketches) to the vertices of a graph, which allow
adjacency, exact distance thresholds, or approximate distance thresholds to be
computed with high probability from the labels.
  Our main results are that, for monotone classes of graphs: constant-size
adjacency sketches exist if and only if the class has bounded arboricity;
constant-size sketches for exact distance thresholds exist if and only if the
class has bounded expansion; constant-size approximate distance threshold (ADT)
sketches imply that the class has bounded expansion; any class of constant
expansion (i.e. any proper minor closed class) has constant-size ADT sketches;
and a class may have arbitrarily small expansion without admitting
constant-size ADT sketches.
