Related, another cool thing that Voronoi graphs are useful for is enumeration all possible paths a robot can take in an environment. This can be used to determine the quality of the map built with sonar/radar/lidar, to better understand the value of a sensor or algorithm in SLAM.
I wrote a paper on it long ago, the third one listed here if you're interested
http://chofter.com/mapviewer/voronoi.php
Pardon my pre-web-engineer lack of HTML knowledge, I was young and mind melded with robots at the time :-)