Relationship between graphs describing horizontal and vertical cell network

Question

In the July 1997 Scientific American issue, Ian Stewart wrote a piece about squared squares (see here):

He uses vertical walls (in bold) as nodes and the squares as edges from which he can build up a directed acyclic graph where the direction goes any wall above to any wall below.

I would like to not only consider the network of vertical walls, but also the network of horizontal walls. Let us call the incidence matrix of the horizontal network $A$ and for the vertical network call it $\hat{A}$.

I think there must be a clear relationship between $A$ and $\hat{A}$. Clearly, the number of edges (squares) is the $m=10$ in both, but the number of walls is different ($n=7$ for $A$ and $n=6$ for $\hat{A}$). Therefore $A$ cannot be the dual graph of $\hat{A}$.

Beyond that, I am not sure what the relationship between $A$ and $\hat{A}$ might be. However, knowing $A$ I think you should be able to work out $\hat{A}$ as a function of $A$, that is $\hat{A}=f(A)$.

Do you think one can always find a unique $f$, and what could its form be?

Answer 1

If you add another edge connecting the first and the last wall (an edge between $1$ and $7$ in the horizontal network, and an edge between $1$ and $6$ in the vertical network) then the two graphs are dual graphs.

For example, the face in the horizontal network bounded by edges $1,3,5,9$ is dual to vertex $2$ in the vertical network, which is incident to edges $1,3,5,9$.

To see that this happens in general, consider a vertex of the horizontal network: a vertical wall. It is bounded on the top and bottom by horizontal walls, and is potentially incident to several more horizontal walls in the middle. In the vertical network, those horizontal walls become vertices all connected by edges, and so the vertical wall becomes a face of the vertical network.

The first and last wall need to be treated separately, because the description above isn't true for them, but if we add an edge between them, then everything works out.

Answer 2

Just an extended comment on Misha's answer.

Thank you for pointing out the duality between the horizontal and vertical graph with the addition of artificial edges. It is very helpful! To make this clearer to myself, I constructed the following simple example:

A shows a simple example network and B shows the horizontal graph. I have sketched the "ghost edge" and "ghost cell" in dashed lines. I call the amended horizontal incidence matrix (i.e. including ghost edge) $A_+$ and give its transpose. C shows the vertical graph with ghost objects in dashed, and I provide the amended vertical incidence matrix $\hat{A}_+$. Finally, D shows the duality of the amended horizontal and vertical graphs.

I think the second part of my question still stands, perhaps I can now state it in a slightly more precise way:

The horizontal graph has incidence matrix $A\in\left\{ -1,0,1\right\} ^{m\times n}$ and the vertical graph has incidence matrix $\hat{A}\in\left\{ -1,0,1\right\} ^{m\times\hat{n}}$. Their amended counterparts (with ghost edges) are $A_{+}\in\left\{ -1,0,1\right\} ^{\left(m+1\right)\times n}$, $\hat{A}\in\left\{ -1,0,1\right\} ^{\left(m+1\right)\times\hat{n}}$. Given the incidence matrix $A_{+}$, is there a map $\hat{A}_{+}=f\left(A_{+}\right)$ that allows me to construct the incidence matrix $\hat{A}_{+}$ of the dual graph for this cell network problem? Would the map be invertible?