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
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/11347
0 comments:
Post a Comment
Let us know your responses and feedback