Generate Voronoi graph with the method mentioned in the paper "A Plane Sweep Algorithm for the Voronoi Tessellation of the Sphere".
http://www.e-lc.org/tmp/Xiaoyu__Zheng_2011_12_05_14_35_11.pdf
Check http://whenitsdone.org/2014/07/29/map-generation-on-spherical-planet-part-i/ for an example of the result.