Here's my first attempt; it's got some extra goodies in it, but the premise is pretty much the same. The only real abstraction is the creation of the graph. The mechanics of the algorithm are still here:

# my $g = Graph->new_from_degree_sequence(\@degrees, \@vertices);
# my ($g, $iters) = Graph->new_from_degree_sequence(\@deg, \@vert);
# the vertices are optional

sub new_from_degree_sequence {
  my ($class, $deg, $vert) = @_;
  my $sorted = 1;

  # determine the sortedness of the degree sequence,
  # and do a checksum while we're at it
  {
    my $odd = $deg->[0] & 1;

    for (1 .. $#$deg) {
      $sorted &&= 0 if $deg->[$_] > $deg->[$_-1];
      $odd = !$odd if $deg->[$_] & 1;
    }

    $@ = "sum of degrees (@$deg) is odd", return if $odd;
  }

  # determine if the vertices are references,
  # and install default vertex names if needed
  my $ref = 0;
  if ($vert) { for (@$vert) { $ref = 1, last if ref } }
  else { $vert = [map chr(64 + $_), 1 .. @$deg] }

  # create the graph, and store the vertex-degree info
  my $graph = Graph::Undirected->new(vertices => $vert, refvertexed =>
+ $ref);
  my @v = map [$vert->[$_], $deg->[$_]], 0 .. $#$vert;

  my $iter = 0;

  # continue while there are still vertices left to connect
  # only sort the remaining vertices if they weren't already sorted
  while (@v and ($sorted ||= (@v = sort { $b->[1] <=> $a->[1] } @v))) 
+{
    # if we don't have enough vertices, stop
    $@ = "impossible degree sequence (@$deg)", return if @v < $v[0][1]
+;

    ++$iter;

    # connect the vertex with the highest degree (N)
    # to N other vertices with the highest degrees
    for (my $i = $v[0][1]; $i >= 1; --$i) {
      $graph->add_edge($v[0][0], $v[$i][0]);
      --$v[$i][1] or splice @v, $i, 1;
    }

    shift @v;

    # see if the remaining vertices need sorting
    for (1 .. $#v) { $sorted = 0, last if $v[$_][1] > $v[$_-1][1] }
  }

  return wantarray ? ($graph, $iter) : $graph;
}
[download]