Is every planar graph a possible dual graph of a voronoi diagram? 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?
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.