I've worked with fairly large graphs in connection with Y2K analysis.

I used GraphViz for a start, but increasingly switched to yED for faster generation, more flexible and interactive layout, graph partitioning and analysis, -- and more.

There's no Perl interface to yED, but it's simple (in Perl :) to generate the raw graph data files in GraphML, GML or a 'free form' XML & XSLT format of your choice.

Best regards
allan dystrup