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.


The standard answer for this type of question would be: use a planarity testing algorithm. This graph has a unique planar embedding and there are algorithms for finding it in linear time. But that's overkill for this problem.

A square grid is a special case of a squaregraph, and in my paper "Combinatorics and geometry of finite and infinite squaregraphs" I have a Lexicographic-BFS based algorithm for recognizing squaregraphs without the overhead of going through planarity testing. It would also solve your problem. But it's still overkill.

Instead I suggest:

  • Find a vertex s of degree two.
  • Do a breadth first search starting from s.
  • In the breadth first search, whenever you are processing a vertex v and there are two neighbors of v that are not yet in the queue and need to be added, the one to add first is the one that doesn't have any other neighbors already in the queue.

Then the levels of the breadth first search tree, in the order given by this search, should be exactly the diagonals of your grid. Once you have this ordering, assigning numbers to the vertices should be trivial.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.