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.