I'm reading up on NP hard problems in Unit Disk graphs. I'd like to point out i'm fairly new to this NP hard stuff so i'm trying to get around how to prove something is NP hard.

The following lemma 2.1 is used

Lemma 2.1 (Valiant [19]). A planar graph $G$ with maximum degree 4 can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at integer coordinates and its edges are drawn so that they are made up of line segments of the form $x=i$ or $y=j$,for integers $i$ and $j$.

So in particular i'm now reading the section on UD vertex cover being NP hard (page 172)

THEOREM: UD Vertex cover is NP-Complete

Proof. The reduction is from PLANAR VERTEX COVER with maximum degree 3, which was shown NP-complete in [4]. As before, we transform the planar graph $G$ with maximum degree 3 to a unit disk graph $G’$ such that $G$ has a vertex cover $S$ with $|S|\leq k$ if and only if $G’$ has a vertex cover $S’$ with $|S'|\leq k’$.

We draw $G$ in the plane using Lemma 2.1. We then replace each edge $\{u, v\}$ by a path having an even number $2k_{uv}$,, of intermediate vertices, in such a way that an intersection model can be constructed. (This is clearly easy to do. Note, however, that a grid graph embedding will not be possible unless G is bipartite, which is why this construction does not work for grid graphs.) It is straightforward to verify that $G$ has a vertex cover $S$ such that $|S| <k$ if and only if $G’$ has a vertex cover $S’$ such that $|S'|\leq k+\sum_{uv \in E(G)} K_{uv}$.

In trying to digest the proof i have the following questions.

How are the disks in $G'$ placed on the edges of $G$? It says they form a path so would each disk added have two other neighbours in front and behind of it or could some be say stacked almost on top of each other.

Why can a grid graph not be embedded? Technically we can transform a planar graph into a grid like structure using lemma 2.1 so why cannot we just add intermediate points on the edges of $G$ to form a grid? I'm especially interested in this question because i would like to know why this technique cannot be reapplied in other cases?