§ 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×H. So we havethe vertex set as V≡{(w,h)1≤w≤W,1≤h≤H}.We have in the edge set all elements of the form ((w,h),(w±1,h±1))as long as respective elements (w,h) and (w±1,h±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∈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.