Background
Hamiltonian circuit problem is a decision problem which asks whether a given graph has a Hamiltonian circuit, i.e. a cycle that visits every vertex exactly once. This problem is one of the well-known NP-complete problems.
It is also known that it remains so when restricted to grid graphs. Here, a grid graph is a graph defined by a set of vertices placed on 2D integer coordinates, where two vertices are connected by an edge if and only if they have Euclidean distance of 1.
For example, the following are an example of a grid graph and an example of a graph that is not a grid graph (if two vertices with distance 1 are not connected, it is not a grid graph):
Grid graph Not
+-+ +-+
| | |
+-+-+-+ +-+-+-+
| | | | |
+-+-+ +-+-+
NP-complete problems are reducible to each other, in the sense that an instance of problem A can be converted to that of problem B in polynomial time, preserving the answer (true or false).
Challenge
Given a general undirected graph as input, convert it to a grid graph that has the same answer to the Hamiltonian circuit problem in polynomial time. Note that you cannot solve the problem on the input directly, unless P=NP is proven to be true.
A graph can be input and output in any reasonable format. Additionally, a list of coordinates of the grid graph is a valid output format.
Standard code-golf rules apply. The shortest code in bytes wins.
