# Reconstructing a 2D lattice graph from an unordered adjacency list

Is there any kind of algorithm that can map a set of points and their unordered adjacent neighbours to a 2D lattice graph that would then be addressable using X, Y coordinates?

For example, given the following input information:

point    neighbours (unordered!)

a        d, b
b        a, c, e
c        f, b
d        e, a, g
e        d, f, b, h
f        i, c, e
g        d, h
h        g, i, e
i        f, h


Then the algorithm would generate a 2D array like so:

point    coordinate

a        (0, 0)
b        (0, 1)
c        (0, 2)
d        (1, 0)
e        (1, 1)
f        (1, 2)
g        (2, 0)
h        (2, 1)
i        (2, 2)


Which would correspond to the following layout:

 a      b      c
*------*------*
|      |      |
|d     |e     |f
*------*------*
|      |      |
|g     |h     |i
*------*------*


Unfortunately the size of the graph is not known beforehand. Likewise, there is a possibility that the sides of the graph might be circular in nature (like a tube or toroid), in which case I would need to be able to pick a point that the rest of the graph is aligned to as 0, 0 (but the direction the graph travels from there isn't important, so long as I can still address the individual points in X, Y coordinates).

Speed is somewhat important, since the adjacency lists are anywhere from 40 to ~1.8M entries long. The fewer times I have to iterate through that, the better. I have constant lookup time for any given point within the adjacency list, so getting the neighbours for any given point is reasonably fast.