External Memory BFS on Undirected Graphs with Bounded Degree

We give the first external memory algorithm for breadth-first search (BFS) which achieves $o(n)$ I/Os on arbitrary undirected graphs with $n$ nodes and maximum node degree $d$. Let $M$ and $B>d$ denote the main memory size and block size, respectively. Using $\mathrm{Sort}(x)=\Theta(\frac{x}{B}\cdot \log_{M/B}\frac{x}{B})$, our algorithm needs ${\cal O}(\frac{n}{\gamma \cdot \log_d B} + \mathrm{Sort}(n \cdot B^\gamma))$ I/Os and ${\cal O}(n \cdot B^\gamma)$ external space for an arbitrary parameter $0 <\gamma \le 1/2$. The result carries over to BFS, depth-first search (DFS) and single source shortest paths (SSSP) on undirected planar graphs with arbitrary node degrees