Just like in this answer, perturbation with one-dimensional Perlin noise can be used to draw fuzzy-looking lines. Here is one way of going about it:
fBm = With[{permutations =
Apply[Join, ConstantArray[RandomSample[Range[0, 255]], 2]]},
Compile[{{x, _Real}},
Module[{xf = Floor[x], xi, xa, u, i, j},
xi = Mod[xf, 32] + 1; xa = x - xf;
u = xa*xa*xa*(10. + xa*(xa*6. - 15.));
i = permutations[[permutations[[xi]] + 1]];
j = permutations[[permutations[[xi + 1]] + 1]];
(2 Boole[OddQ[i]] - 1)*xa*(1. - u) +
(2 Boole[OddQ[j]] - 1)*(xa - 1.)*u],
RuntimeAttributes -> {Listable}]];
handdrawn[p1_, p2_, fr_, sh_, divisor_, n_] := With[{cs = Normalize[p2 - p1]},
BSplineCurve[Table[(1 - t) p1 + t p2 +
{0, fBm[fr (10 t + sh)]/ divisor}.{cs, Cross[cs]},
{t, 0, 1, 1/n}]]]
The handdrawn[]
edge function can then be used like so:
PetersenGraph[5, 2,
EdgeShapeFunction -> Function[{pts, e},
handdrawn[pts[[1]], pts[[2]],
20, 1/10, 30, 51]],
EdgeStyle -> Directive[AbsoluteThickness[3], ColorData[61, 8]],
VertexStyle -> ColorData[61, 8]]

The only caveat of handdrawn[]
is that tweaking the last four parameters is usually needed to arrive at a satisfactory-looking fuzzy line.
xkcdConvert
seems to work with graphs, though it takes an atrociously long time and it's hard to say if that's the kind of result desired. $\endgroup$ – LLlAMnYP Oct 21 '15 at 11:49