Graph is described in detail in the book "Algorithms in Perl" from o'reilly (the author of the book also wrote the module)

But I'm not sure that its worth buying that book for just the graph theory chapter, though. But then, I'm kind of ambivalent about both (the book and the modules).