Problem Detail: 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?
Asked By : user695652
Answered By : mhum
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 
The blue lines and circles are $mathcal{G}$ and the red crosses are $C$. EDITED TO ADD: An example with a biconnected graph Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/11347 3.2K people like this
