Adjacency labeling schemes and induced-universal graphs

Stephen Alstrup, Haim Kaplan, Mikkel Thorup +1

We describe a way of assigning labels to the vertices of any undirected graph on up to $n$ vertices, each composed of $n/2+O(1)$ bits, such that given the labels of two vertices, a…