How to create a map from graph

Question

I want to draw a 2d polygon map based on data provided by another source to ease analysing actions on the map. The data has the following format:

1 ['2', '4', '5', '7', '17', '10']
2 ['1', '3', '4']
3 ['2', '11', '4']
4 ['1', '2', '3', '11', '13', '18', '5']
5 ['1', '4', '18', '17']
6 ['7', '8']
...

The first number is the ID of a node, the following list contains the IDs of its neighbours. As a node's number of neighbours differs I need to draw a polygon map.

So I tried to use Voronoi polygons for the map representation. The problem is: How can I determine the points to satisfy all neighbourhood relations? I guess my first try is more or less an error in my try and error cycle. I used the sfdp tool of graphviz to get the point positions of the graph:

Using the positions of the points resulted in the following map representation:

The problem of this approach is that for example nodes 4 and 1 are neighbours but in the Voronoi diagram they aren't because of the position of the nodes. So for me this approach failed.

Googling, I found a lot of tutorials generating maps with polygons or tiles but I haven't found out yet how I can create a map for my given data. I guess there is an approach using (multiple) hexagons/triangles/squares or a mixture to achieve what I need but I don't know what I shall search for.

Is there a keyword or an algorithm which can help me here?

Update/Result: For completeness: This is my result after using the suggestions of the accepted answer:

Answer 1

What you want is to produce a dual graph; that is, a graph produced by converting faces to vertices, and connecting them based on adjacent faces in the original graph. Example:

The problem, as you can see, is that if you want to keep the same layout of the graph, you'll get some really curvy edges in the dual graph. Also, you'll often end up with a multigraph - a graph where some vertices have multiple edges between them. It is guaranteed to be planar though, so that's something.

To use your example, we can produce the dual graph in the following steps:

Step 1: For each face in the original graph, create a vertex

Note that we create an outer "ring" to represent the outermost "vertex" - this is so we can have a nicer looking graph at the end, without the crazy curvy edges.

Step 2: For each edge in the original graph, connect the two face-vertices with an edge

Also, you're going to have to do something about these edges not overlapping each other. The gap between 3 and 12 is especially problematic. These new edges may need to be bendy to make this possible. It's what you get for having a concave graph.

Step 3: Play Risk

Answer 2

If the first image, where each point is a small square with certain color, is what you are searching for, you need to build the Delaunay's triangulation.