Consider a graph $G = (V,E)$ and the following operation
$\text{neighbour}(v_1,v_2)$: returns true
if the vertices $v_1$ and $v_2$ are adjacent, and false
otherwise.
I now consider two standard data structures:
Adjacency Matrix. Space complexity is $\mathcal{O}(|V|^2)$ and supports the neighbour-query in $\mathcal{O}(1)$ time.
Adjacency List. Space complexity is $\mathcal{O}(|E| + |V|)$ as far as I understand, however the neighbour-query depends on the degree size.
My question is the following:
How can we improve these data structures using hashing? (space/time complexity in terms of $|V|$ and $|E|$)
Can we e.g. reduce the space complexity of the adjacency matrix and retain an average constant time query?