# 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 cam 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-* 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.

**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

in the matrix of boundary distances.