I've implemented fairly complex graphs with RDBMS, for instance MySQL. Class::DBI makes for a nice interface.

The disadvantage is the lack of speed, of course. You could use a file-based RDBMS such as SQLite, or a pure file-based database without RDBMS features such as BerkeleyDB. Those may be adequate to your needs. If you are just storing nodes and edges without any complex attributes, you may be able to get away with BerkeleyDB.

You can probably hack the Graph module to integrate it with a RDBMS system.

Ted