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?

Improve this question
$\endgroup$
2
  • $\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
    Commented Apr 17, 2013 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
    Commented Apr 17, 2013 at 15:49

1 Answer 1

Reset to default
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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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