§ Discrete schild's ladder

If one is given a finite graph $(V, E)$, which we are guaranteed came from discretizing a grid, can we recover a global sense of orientation?

• More formally, assume the grid was of dimensions $W \times H$. So we havethe vertex set as $V \equiv \{ (w, h) 1 \leq w \leq W, 1 \leq h \leq H \}$.We have in the edge set all elements of the form $((w, h), (w \pm 1, h \pm 1))$as long as respective elements $(w, h)$ and $(w \pm 1, h \pm 1)$ belong to $V$.

• We lose the information about the grid as comprising of elements of theform $(w, h)$. That is, we are no longer allowed to "look inside". All wehave is a pile of vertices and edges $V, E$.

• Can we somehow "re-label" the edges $e \in E$ as "north", "south", "east",and "west" to regain a sense of orientation?

• Yes. Start with some corner. Such a corner vertex will have degree 2. Now,walk "along the edge", by going from a vertex of degree 2 to an neighbourof degree 2. If we finally reach a vertex that has unexplored neighbours of degree 3 or 4, pick the neighbour of degree 3. This will giveus "some edge" of the original rectangle.

• We now arbitrary declare this edge to be the North-South edge. We now needto build the perpendicular East-West edge.

• This entire construction is very reminisecent ofSchild's Ladder