Transformando una cubierta arbitraria en una cubierta de vértice

Dado es un gráfico plano y deje que G denote su incrustación en el plano st cada borde tiene una longitud 1 . Tengo además un conjunto C de puntos en los que cada punto c ∈ C está contenido en G . Además, para cualquier punto p en G, existe un c ∈ C con una distancia geodésica a p como máximo uno. (La distancia se mide como la distancia más corta dentro de G ).$G=(V,E)$$\mathcal{G}$$1$$C$$c \in C$$\mathcal{G}$$p$$\mathcal{G}$$c \in C$$p$$\mathcal{G}$

Quiero argumentar que dada una para la cual se cumple la condición anterior, puedo transformarla fácilmente en una cubierta de vértice, o decirlo de otra manera, transformarla en una C ' de la misma cardinalidad st cualquier c ∈ C ' se coloca en G en un vértice de G , y C ' todavía cubre G .$C$$C'$$c \in C'$$\mathcal{G}$$G$$C'$$G$

Mi enfoque fue orientar los bordes y mover los puntos en en el vértice final del arco. Pero hasta ahora no he encontrado una orientación correcta que produce C ' de C .$C$$C'$$C$

Alguien tiene una idea?

Si no hay puntos en se encuentran exactamente en el punto medio de una arista en G , entonces es suficiente para asociar cada punto C al vértice más cercano en G . Lo dejaré como ejercicio para que el lector pruebe esto (pista: probar por contradicción).$C$$\mathcal{G}$$C$$\mathcal{G}$

Por otro lado, si se permite que los puntos en se encuentren en el punto medio de los bordes, entonces podemos proporcionar un contraejemplo:$C$

Las líneas azules y los círculos son y las cruces rojas son C .$\mathcal{G}$$C$

EDITADO PARA AGREGAR: Un ejemplo con un gráfico biconnectado