User:DVD206/Medial graphs

The following construction is an important tool in studying the graphs properly embedded into manifolds. One considers an embedded into a surface (2D manifold) finite graph, which vertices have exactly four neighbors. The union of edges of such graph is equal to a union of closed curves on the surface, called geodesics. The faces of the graph can be two-colored. The corresponding graph G and its dual G^* can be obtained by putting vertices in all faces of the same color and connecting two vertices by an edge if the corresponding faces of the medial graph M(G) have a common corner. Note that M(G)=M(G^*).

One can modify the construction accordingly for the case of an embedded graph w/boundary by allowing vertices of the medial graph to have two neighbors.

The following transformations of the geodesics of the medial graph M(G) are similar to the Reidemeister moves of the knot theory. They correspond to the Y- $\Delta$ transformations of the graph G and G^*.

The following matrix consists of the the distances (the smallest number of jumps across the geodesics) between boundary faces of the medial graph below.

{\begin{bmatrix}0&1&2&3&2&3&2&1\\1&0&1&2&3&4&3&2\\2&1&0&1&2&3&4&3\\3&2&1&0&1&2&3&4\\2&3&2&1&0&1&2&3\\3&4&3&2&1&0&1&2\\2&3&4&3&2&1&0&1\\1&2&3&4&3&2&1&0\end{bmatrix}}

Exercise (**). Prove that the distances between boundary faces of an embedded medial graph are invariant under the the geodesics moves.

The geodesics of the medial graph form an arrangement of pseudo-lines if

none of them intersect itself
none of them is a closed curve
no two of them intersect more than once

Exercise (***). Prove that (a) one can recover a planar medial graph M(G), up to the moves, from the distances between its boundary faces, (b) every planar medial graph M(G) can be moved into an arrangement of pseudo-lines without changing the distance matrix.

(Hint). Look for the pattern

{\begin{bmatrix}k+1&k\\k&k+1\end{bmatrix}}

in the matrix of boundary distances.