NP hard problems on UD graphs

Question

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.

http://ac.els-cdn.com/0012365X9090358O/1-s2.0-0012365X9090358O-main.pdf?_tid=482a47e0-6ccc-11e4-882d-00000aacb362&acdnat=1416058716_bd16a516e1bc0a7d9dac8edc15cce221

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.

1. 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.

2. 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?

Answer 1

1. As you want. You can take the disks to be tangent minus a tiny something, or stacked plus a tiny bit. As long as $k_{u,v}$ is big enough, both should work.

2. The comment between parenthesis is a bit vague. A way to understand this that makes sense is the following: Lemma 2.1 allows you to embed every planar graph such that the vertices are placed on a grid. This is probably what they call a grid graph. The comment just points out that this grid graph is not by itself a good starting point for an intersection model with union disks: for example in the poor following ascii example, linking the vertices with unit disks on the first line without touching the ones below is impossible

x--------x

x-x-x-x--x

Hence the need to subdivide the edges.

Edit following the comments. It seems that a grid graph is actually a constraint on the embedding: if we call a grid graph embedding a UD graph with integer coordinates and radii 1/2, then every such embedding is bipartite, so the initial graph must be bipartite as well. This is in my opinion just what they mean in this parenthesis. On the other hand, by subdiving the edges, you can make the graph bipartite, and by choosing the radii small enough (or equivalently by scaling the grid), you do obtain a grid graph embedding of this subdivided graph.