Me estoy volviendo adicto a gPlanarity [1].
[2]
gPlanarity
La idea es sencilla; uno “desenreda” las gráficas hasta que quedan planas (que dos aristas no se intersecten). Todo el programa está hecho con Cairo y es increíblemente sencillo, bonito y divertido. Altamente recomendable.