No finite set of test cases can prove correctness of an algorithm, if we have no information about the form or structure of the algorithm and if the set of possible inputs is infinite.
For any finite set of test cases you might have in mind, I can come up with an algorithm that works correctly on all of those test cases, but is incorrect (works incorrectly on another input, or on infinitely many inputs). For instance, if your test cases are the inputs $t_1,\dots,t_k$, and the correct answers are $y_1,\dots,y_k$, then my algorithm can be:
Algorithm FooledYou(x):
- If $x=t_i$ for some $i$, then output $y_i$. Otherwise, output 42.
This algorithm has polynomial time and works correctly on those $k$ test cases, but is not a correct solution to the problem.
This is a fundamental limitation of using testing to check program correctness. Testing cannot prove a program is correct; it can only prove the program is incorrect.
Now, suppose you want to test your program in practice. Here is a heuristic that will likely be effective. You link to a paper that shows that 1-embeddability is strongly NP-complete, by showing a polynomial-time reduction from 3SAT to 1-embeddability. There are standard ways of generating hard instances of 3SAT. So, use that polynomial-time reduction to convert them into (hard) instances of 1-embeddability, and test whether your algorithm gives a correct answer and solves the corresponding 3SAT problem. Odds are, this will reveal a problem of some sort somewhere.
For instance, one standard way to generate hard 3SAT instances is by using the reduction from Factoring to 3SAT: generate a random 2048-bit RSA modulus (product of two 1024-bit primes), then ask what its factors are. For more details, see Fast Reduction from RSA to SAT and Generating 3SAT circuit for Integer factorization example.
