Transformando uma cobertura arbitrária em uma cobertura de vértice

Dado é um gráfico planar e deixe G denotar sua incorporação no plano em que cada aresta tem comprimento 1 . I têm, além disso, um conjunto C de pontos, em que cada ponto c ∈ C está contido na L . Além disso, é válido para qualquer ponto p em G que exista um c ∈ C com distância geodésica até p no máximo um. (A distância é medida como a menor distância dentro de G ).$G=(V,E)$$\mathcal{G}$$1$$C$$c \in C$$\mathcal{G}$$p$$\mathcal{G}$$c \in C$$p$$\mathcal{G}$

Quero argumentar que, dado um para o qual a condição acima se aplica, posso transformá-lo facilmente em uma cobertura de vértice ou, de maneira diferente, transformá-lo em um C ' da mesma cardinalidade, se qualquer c ∈ C ' for colocado em G a vértice do L , e C ' ainda cobre L .$C$$C'$$c \in C'$$\mathcal{G}$$G$$C'$$G$

Minha abordagem foi orientar as arestas e mover os pontos em no vértice final do arco. Mas até agora eu não encontrar uma orientação correta que produz C ' de C .$C$$C'$$C$

Alguém tem uma ideia?

Se nenhum ponto em mentir exatamente no ponto médio de uma aresta em G , em seguida, basta associar cada ponto C para o vértice mais próximo no G . Vou deixar como um exercício para o leitor provar isso (dica: provar por contradição).$C$$\mathcal{G}$$C$$\mathcal{G}$

Por outro lado, se é permitido que os pontos em fiquem no ponto médio das arestas, podemos fornecer um contra-exemplo:$C$

As linhas azuis e círculos são e as cruzes vermelhas são C .$\mathcal{G}$$C$

EDITADO PARA ADICIONAR: Um exemplo com um gráfico biconectado