If your graph is not one of the ones known to Mathematica then this might help.

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}]

That pins a couple of points to the paper and very rapidly determines returns a couple of choices for positions of some of your subsequent points. You could use that result to fairly quickly determine if there are no satisfactory positions for the rest of your points. Choice of which equations to include has a significant effect on the speed of finding solutions. Sometimes adding an equation will speed it up, others will substantially slow it down. I don't know if you wait long enough whether it would find a solution for all your points.

If your graph is not one of the ones known to Mathematica then this might help.

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}]

That pins a couple of points to the paper and very rapidly determines and returns a couple of choices for positions of some of your subsequent points. You could use that result to fairly quickly determine if there are no satisfactory positions for the rest of your points. Choice of which equations to include has a significant effect on the speed of finding solutions. Sometimes adding an equation will speed it up, others will substantially slow it down. I don't know if you wait long enough whether it would find a solution for all your points.

If your graph is not one of the ones known to Mathematica then this might help.

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}]

That pins a couple of points to the paper and very rapidly determines returns a couple of choices for positions of some of your subsequent points. You could use that result fairly to quickly determine if there is no satisfactory point for the rest of your points. Choice of which equations to include has a significant effect on the speed of finding solutions. Sometimes adding an equation will speed it up, others will substantially slow it down. I don't know if you wait long enough whether it would find a solution for all your points.

If your graph is not one of the ones known to Mathematica then this might help.

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}]

That pins a couple of points to the paper and very rapidly determines returns a couple of choices for positions of some of your subsequent points. You could use that result to fairly quickly determine if there are no satisfactory positions for the rest of your points. Choice of which equations to include has a significant effect on the speed of finding solutions. Sometimes adding an equation will speed it up, others will substantially slow it down. I don't know if you wait long enough whether it would find a solution for all your points.