An O(n) algorithm for realizing degree sequences

A sequence d = (d1, d2, …, dn) of integers is a degree sequence if there exists a (simple) graph G such that the components of d are equal to the degrees of the vertices of G. We present an O(n)-time sequential algorithm to realize d, i.e., to compute the graph G. We provide an efficient parallel implementation of our algorithm.