Computing the degeneracy of large graphs

Any ordering of the nodes of an n-node, m-edge simple undirected graph G defines an acyclic orientation of the edges in which each edge is oriented from the earlier node in the ordering to the later. The degeneracy on an ordering is the maximum outdegree it induces, and the degeneracy of a graph is smallest degeneracy of any node ordering. Small-degeneracy orderings have many applications. We give an algorithm for generating an ordering whose degeneracy approximates the minimum possible, that is, it approximates the degeneracy of the graph. Although the optimal ordering itself can be computed in O(m)time and O(m) space, such algorithms are infeasible for large graphs. Our approximation algorithm is semi-streaming: it uses less space, can achieve a constant approximation ratio, and accesses the graph in logarithmic read-only passes.