My question is: Given a planar graph defined by its adjacency matrix. Can I always find a set of points, so that the dual graph of the voronoi diagram of that set of points is the same as the planar graph?


1 Answer 1


No. The dual graph of a Voronoi diagram is the Delaunay triangulation of its point set so, in particular, every interior face of it is a triangle. But there are plenty of planar graphs (e.g., the $4$-cycle) that have non-triangular interior faces.

  • $\begingroup$ This is not correct. The Delaunay triangulation may not be unique and this breaks the proof. For example, the points $\{(\pm 1,\pm 1)\}$ have Voronoi regions which have the adjacency of a 4-cycle. $\endgroup$ Aug 26, 2022 at 22:19
  • $\begingroup$ However, this answer is still morally correct, in the sense that I think it highlights the right question to ask. Is every triangulated plane graph a dual graph of some Voronoi diagram? I might ask this on mathoverflow if I can't figure it out. $\endgroup$ Aug 26, 2022 at 22:21

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.