I want to find some characteristics for a set of points $S$ which contains $n$ points and has some Voronoi Diagram $V(S)$. This diagram should have exactly $2n-5$ vertices.I tried to use the Euler formula for planar graphs which says $v-e+f = 2$:$\Rightarrow 2n -5 -e + n = 2 \Rightarrow e = 3n-7$ - but what can I now do with the information that $V(S)$ has $3n-7$ vertices?
Voronoi Diagram: Exactly 2n-5 vertices
graph theory;graphs;computational geometry;voronoi diagrams
You made a small mistake by thinking that the Voronoi diagram is a planar graph. Remember that it has those rays that go to infinity. you can make a planar graph out of the Voronoi diagram by adding a new vertex and making all rays incident to this apex. Plugging this into Euler's formula yields$$ 2n-4 - e + n = 2 \quad \Rightarrow \quad  e= 3n - 6.$$A planar graph has $3n-6$ edges if it is a triangulation (this can als be obtained via Euler's formula  just set $3f=2e$). As a consequence the dual graph to your Voronoi diagram (the Delaunay tessellation) is a triangulation. Or phrased differently, every vertex of your Voronoi diagram  has degree~3 and there are three rays.