16
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Apr 17 '13 at 6:20
  • 1
    $\begingroup$ @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 $\endgroup$ – user695652 Apr 17 '13 at 15:49
5
+50
$\begingroup$

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:

enter image description here

The blue lines and circles are $\mathcal{G}$ and the red crosses are $C$.

EDITED TO ADD: An example with a biconnected graph

enter image description here

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user695652 Apr 21 '13 at 4:29
  • $\begingroup$ I don't think bi-connectedness will save you. I've edited my answer with a new example. $\endgroup$ – mhum Apr 22 '13 at 16:50
  • $\begingroup$ This is a rather different question. It might make sense to post it separately. $\endgroup$ – mhum Apr 23 '13 at 0:15
  • $\begingroup$ @mhum How did you make pictures of graphs? Does exists some program to that? $\endgroup$ – Tacet Nov 11 '15 at 14:06
  • $\begingroup$ @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. $\endgroup$ – mhum Nov 11 '15 at 17:25

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.