¿Es todo gráfico plano un posible gráfico dual de un diagrama de Voronoi?

Question

Mi pregunta es: Dado un grafo plano definido por su matriz de adyacencia. ¿Puedo encontrar siempre un conjunto de puntos, de modo que el gráfico dual del diagrama de voronoi de ese conjunto de puntos es el mismo que el gráfico planar?

Answer 1

Lema: dado un diagrama de Voronoi $\mathcal{D}$ y su gráfico dual $(\mathcal{V}, \mathcal{E})$ Consideremos una "cara" del grafo (un componente conexo acotado de su complemento), y el conjunto de todos los vértices en la frontera de esa cara. Entonces todos los sitios de $\mathcal{D}$ correspondientes a estos vértices se encuentran en el mismo círculo.

Corolario: Si el gráfico de abajo fuera el dual de un diagrama de Voronoi, entonces los tres sitios correspondientes a los vértices del centro tendrían que estar todos en dos círculos diferentes lo cual es imposible. Obsérvese que no sólo hay una forma de incrustar este gráfico en el plano, sino que las otras formas fallan ante el mismo argumento.