Often Voronoi diagrams are constructed from their duals, Delaunay triangulations.
The Delaunay triangulation of a point set in $d$ dimensions can be obtained from the convex hull
of a lifting of the points into $d+1$ dimensions. This relationship is explained in many sources,
including [_The Handbook of Discrete and Computational Geometry_][1] (Chapters 22, 23).

Implementing this on your own is quite a project, so you might first investigate what is available.
Qhull performs the computations; see [www.qhull.org][2].
$d$-dimensional Delaunay triangulation computations are part of [CGAL][3], specifically [this module][4].
You could use [polymake][5] to convert from the Delaunay triangulation to its corresponding Voronoi diagram.
Finally, there are papers written on specific versions of your problem, for example:
"An Explicit Solution for Computing the Euclidean $d$-dimensional Voronoi Diagram of Spheres in a Floating-Point Arithmetic," by Marina Gavrilova, 2003, [link here][6].

(Incidentally, "Euclidean graphs" play a relatively minor role in this topic.)


  [1]: http://cs.smith.edu/~orourke/books/discrete.html
  [2]: http://www.qhull.org/
  [3]: http://www.cgal.org/
  [4]: http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Convex_hull_d/Chapter_main.html
  [5]: http://archive.msri.org/about/computing/docs/polymake/index.html
  [6]: http://www.springerlink.com/content/nva8385va1ddaw57/