# Transforming an arbitrary cover into a vertex cover

Given is a planar graph $G=(V,E)$ and let $\mathcal{G}$ denote its embedding in the plane s.t. each edge has length $1$. I have furthermore a set $C$ of points where each point $c \in C$ is contained in $\mathcal{G}$. Furthermore, it holds for any point $p$ in $\mathcal{G}$ that there exists a $c \in C$ with geodesic distance to $p$ at most one. (The distance is measured as the shortest distance within $\mathcal{G}$.)

I want to argue that given a $C$ for which the above condition holds, I can easily transform it into a vertex cover, or put differently, transform it into a $C'$ of same cardinality s.t any $c \in C'$ is placed in $\mathcal{G}$ at a vertex of $G$, and $C'$ still covers $G$.

My approach was to orient the edges and move the points in $C$ at the end vertex of the arc. But so far I did not find a correct orientation which yields $C'$ from $C$.

Does anybody have an idea?

• I don't quite understand the problem. What does "$p$ in $\mathcal{G}$" mean? How exactly do you measure distances? If you mean that $p$ is always on an edge, then it seems that if you put it at either end, then every point at distance at most $1$ from it - namely both endpoints - is still at distance at most $1$ from it. For whatever orientation. Apr 17 '13 at 6:20
• @Yuval Filmus $\mathcal{G}$ is a jordan arc drawing of $G$, i.e. a subset of $\mathhbb{R}^2$.$p \in \mathcal{G}$ just means that the point has to be contained in the drawing and not just anywhere in the plane. The distance is measured as the geodesic distance in $\mathcal{G}$, i.e. the shortest path connecting two points in the drawing. For your last remark, take a 4 cycle and put two points in the middle of the first and third edge. This covers the whole graph, but if you now move one point at its clockwise vertex endpoint and one point at its counter clockwise vertex endpoint it doest cover Apr 17 '13 at 15:49

If no points in $C$ lie exactly on the mid-point of an edge in $\mathcal{G}$, then it suffices to associate each point in $C$ to the nearest vertex in $\mathcal{G}$. I will leave it as an exercise to the reader to prove this (hint: prove by contradiction).

On the other hand, if points in $C$ are allowed to lie on the mid-point of edges, then we can provide a counter-example: The blue lines and circles are $\mathcal{G}$ and the red crosses are $C$.

EDITED TO ADD: An example with a biconnected graph • Thanks a lot for the counterexample. Do you agree that if we restrict the graphs to be biconnected, then the claim is true, even if all points are in the middle? Apr 21 '13 at 4:29
• I don't think bi-connectedness will save you. I've edited my answer with a new example.
– mhum
Apr 22 '13 at 16:50
• This is a rather different question. It might make sense to post it separately.
– mhum
Apr 23 '13 at 0:15
• @mhum How did you make pictures of graphs? Does exists some program to that? Nov 11 '15 at 14:06
• @Tacet I don't remember exactly how I did these. I think the first one might have been MS Paint or GIMP. The second one might be either GIMP or Geogebra.
– mhum
Nov 11 '15 at 17:25