  This work concerns with proving space lower bounds for graph problems in the
streaming model. It is known that computing the length of shortest path between
two nodes in the streaming model requires $\Omega(n)$ space, where $n$ is the
number of nodes in the graph. We study the problem of finding the depth of a
given node in a rooted tree in the streaming model. For this problem we prove a
tight single pass space lower bound and a multipass space lower bound. As this
is a special case of computing shortest paths on graphs, the above lower bounds
also apply to the shortest path problem in the streaming model. The results are
obtained by using known communication complexity lower bounds or by
constructing hard instances for the problem. Additionally, we apply the
techniques used in proving the above lower bound results to prove space lower
bounds (single and multipass) for other graph problems like finding min $s-t$
cut, detecting negative weight cycle and finding whether two nodes lie in the
same strongly connected component.
