# Transforming from neighbour representation to grid representation

Assuming I have a list L of lists. Each list in L has four entries [North, Ost, South, West] which represents the neighbours of a point i on a grid. If the entry is 0, the grid neighbour is not occupied by another point.

For example L[0] = [0,3,8,0].

This means that point 1 (which is represented by the first list in L), has point 3 on the right side and point 8 below. On the left and the top, there is no point, these grid places are not occupied.

I am struggling with transforming from this list L representation to a coordinate representation for each point.

The points can be separated, they can form clusters but they don't have to.

With neighbour, I am only referring to one unit above/below/right/left. Any neighbours further apart are not considered.

I think this problem should be known, but I don't know what I should search for.

This task is part of an optimization problem I am trying to solve with a genetic algorithm. I am looking for the optimal arrangement of points on a grid. Since the solution is translational invariant I am trying to find an intrinsic representation of the points on the grid. The representation above is such a trial. Now I have the problem that I cant map from this intrinsic representation back to the grid representation.

• @D.W I deleted the question on StackOverflow. I also edit the question here. Dec 4 '21 at 21:14

Pick an arbitrary node. Assign it the coordinates $$(0,0)$$. Now run any graph traversal algorithm -- say, depth-first search. When you visit a node, you know its coordinates. Now you can look at its neighbors and assign coordinates to each of its neighbors (if they already have coordinates, check that the old ones and the new ones are consistent; if not, then it's impossible to lay out the graph in the plane), and visit the neighbors (if not already visited). This will let you reconstruct all of the coordinates with running time linear in the size of the graph.