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.

  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?


1 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



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.

  • $\begingroup$ As far as I am aware a grid graph is a graph where only neighbouring vertices are connected (i.e they have Euclidean distance one) does this change anything? $\endgroup$ Nov 17, 2014 at 16:58
  • $\begingroup$ This is probably not the definition used here since any such grid graph is bipartite, which is considered as an exception in their paragraph. $\endgroup$
    – Arnaud
    Nov 18, 2014 at 0:14
  • $\begingroup$ Yes I was thinking the same thing, and you are right grid graphs are defined as unit disk graphs where vertices take integer co-ordinates with radius 1/2 $\endgroup$ Nov 18, 2014 at 11:01
  • $\begingroup$ So just to clarify the graph they obtain by embedding the planar graph into a grid and then adding unit disks onto the edges is NOT in general a grid graph, unless the initial planar graph is bipartite? $\endgroup$ Nov 18, 2014 at 11:24
  • $\begingroup$ @PavanSangha See edit. $\endgroup$
    – Arnaud
    Nov 18, 2014 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.