On 2D Inverse Problems/Medial graphs

The following construction plays an important role in studying the graphs properly embedded into surfaces. One considers an embedded into a surface (2D manifold) finite graph w/vertices each w/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 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^*.

Example of a medial graph on a surface

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*). The construction can be modified accordingly for the case of an embedded graph w/boundary by allowing vertices of the medial graph to have one neighbor.

The three moves of geodesics curves

The following matrix consists of the distances (the fewest number of jumps across the geodesics or the edge distance in M^*(G)) b/w 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 and 5 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 are closed
• 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. See [PU] for a continuous analog of the boundary distance rigidity result.

The following min-cut max-flow result was formulated w/help of Derek Jerina, a student of REU summer school on inverse problems at the University of Washington.

Exercise (**). Prove that the ranks of submatrices of the matrix of the Dirichlet-to-Neumann operator of a planar graph w/natural boundary determine the shortest distances between the boundary faces of its medial graph, and therefore determine the planar graph up to a finite sequence of Y-Δ transformations. (Hint.) It follows from the determinant identity in the section  Special matrices that the ranks of the submatrices count the numbers of disjoint paths connecting boundary nodes of the planar graph.

It was proved in [DeV1], [DeV2] and [CIM] that if the medial graph of a planar network w/natural boundary is an arrangement of pseudo-lines then the conductivities of its edges are uniquely determined by its Dirichlet-to-Neumann operator and can be found by a layer stripping algorithm.