An Mathematiker&Co - Graph & Voronoi Diagram

Ist nicht weltbewegend, aber kennt jemand einen Weg (engl. Paper wäre durchaus okay) mit dem man von einem gegebenen Graphen sagen kann ob es sich bei ihm um ein Voronoi Diagramm handelt?

formaler:
Exisitiert zu gegebenem Graphen G(V,E), grad(ei)=3 für alle ei aus E, (wenns ohne diese Bedingung geht noch besser) eine Knotenmenge S, so dass G das Voronoi Diagramm zu S ist?

(Hab heute schon einige Stunden drüber gegrübelt komme aber auf keine gute Idee.)

Cu Selur

Ps.: wäre vorallem cool, wenn das Ganze in O(n) oder O(n log n) geht.
(frage sonst kommenden Dienstag mal nen Prof. an der Uni,..)

LigH: in "Algorithmen und Datenstrukturen" und auch in "Algorithmische Geometrie" (was ich bevorzuge) steht dazu nix, wenn ich es nicht irgendwie übersehen habe.

Voronoi Diagramme erstellen geht in O(n logn), aber ich will ja quasi die andere Richtung.

Cu Selur

"mal nach pigean hole suchen"
meinste das http://zimmer.csufresno.edu/~larryc/proofs/proofs.pigeonhole.html ?

foolgende Idee ist aufgetaucht:
man packt einfach einen Kreis um den ganzen Graphen
=> man erhält am 'neuen Ende' der früher unendlichen Kanten noch Punkte (deren Kooridnaten man kennt) und durch diese Punkte erhält man auch nochmal einige Gleichungen die wahrscheinlich reichen um das Problem zu lösen,...

Scheint zu klappen,...
(manchmal sieht man den Wald vor lauter Bäumen nicht)

Cu Selur