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.