Looking at the code to Graph, it uses Data::Dumper as for deep copying and dumping. You should therefore be able to dump a Graph object using

sub write_out {
    my $graph = shift;
    my $file = 'graph.dump';
    open my $out', '>', $file or die "Cannot open $file for output: $!
+\n";
    print $out $graph->_dump;
    close $out or die "Could not close output $file: $!\n";
}
[download]

and then you should be able to read it back in again with:

sub read_in {
    my $file = 'graph.dump';
    open my $in', '<', $file or die "Cannot open $file for input: $!\n
+";
    my $Graph;
    local $/ = undef;
    # eval {  <$in> }; # sets $Graph
    eval <$in>; # sets $Graph
    close $in;
    return $Graph;
}
[download]

As an added bonus, the serialised structure is readable (for some definition of readadble...)

update: string eval, not block eval. Note: you want do this only in a trusted environment. String eval is not something to be used lightly.

Maybe you should look at Storable.