Boost Graph Library - бесплатная библиотека C++ для работы с графами.
LEDA - коммерческая библиотека C++, у которой также есть свободная редакция
LEDA Free Edition для некоммерческого использования.
Визуализация графов:
GraphViz - набор бесплатных утилит для редактирования и визуализации графов
LION Graph Visualizer - онлайновая визуализация графов
yFiles (коммерческая)