It is very common to reduce spatial structures (e.g. city maps, country borders, rooms in a building, etc) to graphs that abstract some kind of connectivity. The problem I am trying to solve is about this process in reverse.
Assume you have been given a graph G with n nodes. Is there a way (and how?) to partition a 2D plane into n cells in such a way that for every edge (u,v) in G, the corresponing cells of u and v share borders. (A harder version of this problem can ask for cells to share borders if and only if there is an edge between their corresponding nodes.)
I have exhausted google by searching with different keywords to no success. I would appreciate any help.
Usually, we solve the dual problem instead: how can we draw the graph in the plane, with vertices as points and edges as curves, so that edges do not cross? This is called finding a plane embedding of the graph. (This problem, and your problem as well, are only possible if the graph is planar.) The algorithms to do it are not the most straightforward ones, but at least you should have some keywords to search for, there.
Once you have a plane embedding, here's how you solve your problem. First, make your diagram "thicker", so that the vertices are no longer idealized points but actually small disks, and the edges are not infinitely thin curves but have some small thickness. Not too much thicker, though: we don't want to create any new overlaps between these points and edges.
Second, chop each edge in the middle. To each vertex, assign the following region: the portion of the diagram containing that vertex, and half of each edge out of the vertex. These regions will have exactly the adjacencies you want, but there will also be gaps between them in the plane.
To actually get a partition of the plane, just arbitrarily assign the gaps to any adjacent region. This may introduce some unwanted adjacencies.