§ Discrete schild's ladder

If one is given a finite graph (V,E)(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×HW \times H. So we have the vertex set as V{(w,h)1wW,1hH}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±1,h±1))((w, h), (w \pm 1, h \pm 1))as long as respective elements (w,h)(w, h) and (w±1,h±1)(w \pm 1, h \pm 1) belong to VV.
  • We lose the information about the grid as comprising of elements of the form (w,h)(w, h). That is, we are no longer allowed to "look inside". All we have is a pile of vertices and edges V,EV, E.
  • Can we somehow "re-label" the edges eEe \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 neighbour of 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 give us "some edge" of the original rectangle.
  • We now arbitrary declare this edge to be the North-South edge. We now need to build the perpendicular East-West edge.