Is there a better-than-brute-force algorithm to generate a graph whose relation is string edit distance=1?
In the worst case any such algorithm will work $\Omega(n^2)$ because your graph can have $\Omega(n^2)$ edges.

By the way, are you interested in some particular string metric?