Color Voronoi graphs

To color Voronoi graphs using the algorithm here https://github.com/stefanutti/maps-coloring-python, it is necessary to do some adjustments first:

• Transform it into a 3-regular graph, by adding a frame and modifying the vertices with more than 3 edges, as shown below
• Consider the surrounding area (out of the frame) as part of the map (the ocean) and color also that

It is known that we can also suppose that exactly three edges meet at each vertex since maps that have vertexes with more than three edges can be easily simplified without affecting the search of the coloring. In other words, if you can find a coloring for the map on the right, you can use the same coloring for the original map on the left.

Here is an example of these steps applied to the following Voronoi diagram. Three vertices have a degree greater than three.

Voronoi to 3-regular graph