Representing graphs implicitly using almost optimal space (Q5928875)

The authors present a new graph labelling scheme that assigns to each vertex \(v\) of degree \(\delta(v)\) of a graph of order \(n\) a \(O(\delta(v)\log^2n)\) bit label. The adjacency test can be performed in seven steps and the entire scheme can be computed in polynomial time. In addition, the scheme is implicit (without pointers).