search (BFS) which breaks the Omega(n) I/O bound on arbitrary
undirected graphs with n nodes and constant maximum node degree d.
Our algorithm needs O( n * (1+a) / (b * log_d B) ) I/Os
for main memory size M, n <= M^{1+a}, block size B <= M^{1-b}
and arbitrary constants a,b > 0. The result carries over to
single source shortest paths (SSSP) on undirected planar
graphs with bounded degree.