Is there a better-than-brute-force algorithm to generate a graph whose relation is string edit distance=1? I'm interested in creating a graphs whose vertices are strings, and whose edges represent the relation of having an edit distance of 1 under a given string metric.

An obvious approach is to make all $\frac{n^2-n}{2}$ comparisons among the $n$ vertices, giving us $O(n^2)$ time complexity.

Excluding parallelizing the comparisons, is there a better algorithm in terms of time complexity?

I'm interested in string metrics where strings of different length are allowed.
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?