UnitDistanceQ[input_]:=Module[
    {g, x, F, v, min, nod, gl},
    g = input;
    gl = Length[g]; (* Vertex Count *)
    (* 2 vertex count variables x1, x2, etc... *)
    x = Table[Symbol@@ToExpression["x" <> ToString[i]], {i, 1, 2*gl}];
    (* The force to minimize is the squared error of the lengths *)
    F = !(
*UnderoverscriptBox[([Sum]), (i = 1), (gl)](
*UnderoverscriptBox[([Sum]), (j = 1), (gl)]g[[i, j]] ((((x[[2  i]] - x[[2  j]]))^2 + ((x[[2  i - 1]] - x[[2  j - 1]]))^2 - 1))^2));
    (* Initial vertex positions *)
    v = Table[gl*Random[], {i, 1, 2*gl}];
    (* Minimization *)
    {min, nod} = FindMinimum[F, Transpose[{x,v}], Method->"QuasiNewton"];
    (* Output Solution *)
    If[min < 10^-3,
        Print[{min,nod}];
        GraphPlot[g, VertexCoordinateRules ->
            Thread[Range[gl] -> Partition[ x /. nod, 2]],
        AspectRatio -> Automatic,
        VertexLabeling -> None,
        ImageSize->Small]
    ]
]

g = Graph[
          UndirectedEdge @@@ {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 6}, {3,
             8}, {4, 5}, {4, 9}, {4, 10}, {5, 6}, {5, 10}, {6, 7}, {6,
             10}, {7, 8}, {7, 10}, {8, 9}, {8, 10}, {9, 10}}];
    m = AdjacencyMatrix[g];
    UnitDistanceQ[m]
    (* gives
        FindMinimum::sdprec: Line search unable
             to find a sufficient decrease in the function value with
             MachinePrecision digit precision. >>
*)

isUnitDistance[graph_] := Module[
  {verts, edges, n, coords, p, x, soln},
  verts = VertexList[graph];
  edges = EdgeList[graph];
  n = Length[verts];
  verts = verts /. Thread[verts -> Range[n]];
  coords = Array[x, {n, 2}];
  {x[1, 1], x[1, 2], x[2, 1], x[2, 2]} = {0, 0, 1, 0};
  p[j_] := {x[j, 1], x[j, 2]};
  polys =
   Map[(p[#[[1]]] - p[#[[2]]]).(p[#[[1]]] - p[#[[2]]]) - 1 &, edges];
  Quiet[soln = NSolve[polys]];
  If[soln === {}, False, True]
  ]

SeedRandom[111111];
gg = Graph@
  Union[Sort /@ (RandomInteger[{1, 8}, {20, 2}] /. {j_, j_} :>
       Sequence[])]

GraphData["GolombGraph"]
GraphData["GolombGraph", "UnitDistance"]

Cases[{#, GraphData[#, "UnitDistance"]} & /@ GraphData[], {g_, True} :> g]
Length@%

e = {(x1 - x2)^2 + (y1 - y2)^2 == 1, (x1 - x3)^2 + (y1 - y3)^2 == 1,
     (x1 - x4)^2 + (y1 - y4)^2 == 1, (x2 - x3)^2 + (y2 - y3)^2 == 1,
     (x4 - x5)^2 + (y4 - y5)^2 == 1, (x5 - x6)^2 + (y5 - y6)^2 == 1,
     (x6 - x7)^2 + (y6 - y7)^2 == 1, (x7 - x8)^2 + (y7 - y8)^2 == 1,
     (x8 - x9)^2 + (y8 - y9)^2 == 1, (x9 -x10)^2 + (y9 -y10)^2 == 1,
     x1 == 0, y1 == 0, x2 == 1, y2 == 0};
Reduce[e, {x1,y1,x2,y2,x3,y3,x4,y4,x5,y5,x6,y6,x7,y7,x8,y8,x9,y9,x10,y10}]

Meas[G_, i_: 0] := Module[{
 Ex = EdgeList[G],
 P = N[PropertyValue[{G, #}, VertexCoordinates] & /@ VertexList[G]]
},
Return[If[i == 0,
 Max[Abs[
  Map[Norm[#[[1]] - #[[2]]] &,
   Map[P[[#]] &, Map[List @@ # &, Ex], 1], 1] - 1]],
  Max[Abs[
   Map[Norm[#[[1]] - #[[2]]] &, Map[P[[#]] &, Map[List @@ # &,
       Select[Ex, MemberQ[#, i] &]
       ], 1], 1] - 1]]
 ]]
];

STEP[G_, [Epsilon]_: 0.05, [Delta]_: 0.1] := Module[{
 Vx = VertexList[G],
 Ex = EdgeList[G],
 n, m, P, i, G2, P2
 },
n = Length[Vx]; m = Length[Ex];
P = PropertyValue[{G, #}, VertexCoordinates] & /@ Vx;
P2 = P;
i = RandomInteger[{1, n}];
P2[[i]] = P2[[i]] + [Delta] ({RandomReal[], RandomReal[]} - 0.5);
G2 = Graph[Vx, Ex, VertexCoordinates -> P2];
If[Meas[G2, i] < Meas[G, i] || RandomReal[] < [Epsilon], Return[G2], Return[G]
]]

G = RandomGraph[{15, 20}];
P = Table[{RandomReal[], RandomReal[]}, {q, 1, Length[VertexList[G]]}];
G = Graph[G, VertexCoordinates -> P];
DATA = NestList[STEP, G, 5000];
Manipulate[DATA[[i]], {i, 1, Length[DATA], 1}]

G = GraphData["GolombGraph"];
P = Table[{RandomReal[], RandomReal[]}, {q, 1, Length[VertexList[G]]}];
G = Graph[VertexList[G], EdgeList[G], VertexCoordinates -> P];
DATA = NestList[STEP[#, 0.01, 0.2] &, G, 500000];
Animate[ColumnForm[{DATA[[i]], Meas[DATA[[i]]]}], {i, 1, Length[DATA],1}]