Map from planar graph

I'll describe the steps I took below this picture...

Step 1: start with a planar graph

Step 2: Plot the midpoints of every line connecting points of the graph

Step 3: Connect midpoints that are connected to the same vertex of the original graph, also draw new lines around vertices on the outside of the graph. to those midpoints. This will leave some regions without a vertex from the original graph inside, color those black....

Step 4. Draw lines from the vertices of the black regions to their centroid. 

Step 5. These new lines in addition to those you had drawn around the outside of the graph complete the map.