User:DVD206/Printed Version/Graphs on surfaces

The following construction plays an important role in studying the graphs properly (with well defined faces) embedded into surfaces & 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-$\Delta$ transformations of the graph G and G^*.

The three moves of geodesics curves

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

${\begin{pmatrix}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{pmatrix}}$

Two examples of boundary isometric medial graphs with 4 geodesics

Exercise (**). Prove that the distances between boundary faces of an embedded medial graph are invariant under 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{pmatrix}k+1&k\\k&k+1\end{pmatrix}}$

in the matrix of boundary distances.