# Recreate a spanning tree in a grid graph given vertex descriptions Let's assume I have graph above with spanning tree pointed out by blue edges.

Vertex at position (1,1) (row 1, column 1) is connected to the bottom vertex and has degree 1.

Vertex at position (4,2) (row 4, column 2) is connected to the up, left and right vertex and has degree 3.

Let's call (up, down, left, right) a description of a vertex. For a vertex that is connected to a vertex above it and a vertex left to it, description is (1, 0, 1, 0). For a vertex that is connected to a vertex above, below, left and right to it, description is (1, 1, 1, 1).

Given an array of descriptions of vertices that belong to a spanning tree of a grid graph, dimensions of the grid, recreate a spanning tree that decodes to a given array of descriptions.

For example, for the image above an input to the algorithm could be:

[
(0, 0, 1, 0),  # this one describes vertex at position (4, 4), it is connected to the vertex on the left
(1, 0, 1, 1),  # vertex (4, 2)
(0, 1, 1, 0),  # vertex (2, 4)
(1, 0, 1, 1),  # vertex (2, 3)
(1, 0, 1, 1),  # vertex (2, 2)
(1, 0, 0, 1),  # vertex (2, 1)
(0, 1, 0, 0),  # vertex (1, 2)
(0, 1, 0, 0),  # vertex (3, 1)
(0, 1, 0, 1),  # vertex (1, 3)
(1, 0, 1, 0),  # vertex (3, 4)
(0, 1, 0, 0),  # vertex (1, 1)
(0, 1, 0, 1),  # vertex (3, 2)
(0, 0, 1, 0),  # vertex (1, 4)
(0, 0, 1, 1),  # vertex (4, 3)
(0, 0, 1, 1),  # vertex (3, 3)
(1, 0, 0, 1),  # vertex (4, 1)
]


One of the possible outputs can be (reordered array of descriptions, but I can go over each description and color the edges in an empty grid and get the image above):

[
(0, 1, 0, 0),  # vertex (1, 1)
(0, 1, 0, 0),  # vertex (1, 2)
(0, 1, 0, 1),  # vertex (1, 3)
(0, 0, 1, 0),  # vertex (1, 4)
(1, 0, 0, 1),  # vertex (2, 1)
(1, 0, 1, 1),  # vertex (2, 2)
(1, 0, 1, 1),  # vertex (2, 3)
(0, 1, 1, 0),  # vertex (2, 4)
(0, 1, 0, 0),  # vertex (3, 1)
(0, 1, 0, 1),  # vertex (3, 2)
(0, 0, 1, 1),  # vertex (3, 3)
(1, 0, 1, 0),  # vertex (3, 4)
(1, 0, 0, 1),  # vertex (4, 1)
(1, 0, 1, 1),  # vertex (4, 2)
(0, 0, 1, 1),  # vertex (4, 3)
(0, 0, 1, 0),  # vertex (4, 4)
]


The array can come in any order (there is no way to know for which position the description is). Of course, vertices in the first row can never be connected to a vertex above (there is no row above), similarly, vertices in the last row, first column, last column, cannot be connected to vertices below, left, or right, respectively.

Is there an efficient algorithm that will recreate the spanning tree or enumerate all possible spanning trees that decode to the given descriptions array.

I think that from the given array there are multiple spanning trees of a grid graph (the array does not uniquely define the spanning tree shown on the picture). Similarly, if I was given a sorted degree array [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3] (decoded from the image above), I could construct a variety of trees that satisfy this degree array but some of these trees would not span a grid.

Problem is related to the game described here https://math.stackexchange.com/questions/3191645/uniqueness-of-spanning-tree-on-a-grid/3191756 but there one can rotate things, here, we just have shuffled grid and need to recreate some spanning tree of the grid by repositioning the elements.

• I don't understand the problem statement. What is the input to the algorithm? What is meant by "(up,down,left,right) description of each vertex"? What do you want the algorithm to output? You say "recreate the spanning tree", but which spanning tree do you want and how is it related to the input? You say "satisfy the connected properties" but you don't define what you mean by that; please specify clearly what properties you have in mind. Can you share the motivation for this task or the context where you encountered it?
– D.W.
May 31, 2022 at 2:07
• @D.W. I have added a fully worked out example. May 31, 2022 at 7:10
• Is the grid graph known and given as input? In particular, is the number of rows and columns known / given as input?
– D.W.
May 31, 2022 at 19:14
• Yes, grid dimensions are known. May 31, 2022 at 21:21

Why? Suppose you have a $$m\times n$$ grid graph, where $$m>2$$ and $$n>2$$. Then the number of spanning trees of this grid graph is exponential in $$mn$$. However, the number of possible inputs is at most $$(nm+1)^{16}$$, since there are 16 descriptions and for each description we have a count that ranges from $$0$$ to $$nm$$. The latter number is polynomial in $$nm$$, so when $$nm$$ is large, we find that the number of possible spanning trees vastly exceeds the number of possible inputs.