Last modified on 8 March 2013, at 21:22

On 2D Inverse Problems/Graphs and manifolds

Throughout this book a graph G(V,E) is a pair of sets, where E is a subset of pairs of elements of the set V. The elements of V are called vertices, and the elements of E edges. For every edge (a,b) in E we call b a neighbor of a. A graph w/boundary is a graph w/chosen subset ∂G of boundary nodes.

A surface S is a topological space, such that around its every point p there is an open set U homeomorphic to the open unit disc D:


\begin{cases}
p\in U, \\
\phi_U(p) = 0, \\
\phi_U(U) = \mathbf{D}.
\end{cases}

or neighborhood homeomorphic to the half of the unit disc for the boundary nodes:


\begin{cases}
p\in U, \\
\phi_U(p) = 0, \\
\phi_U(U) = \mathbf{D}\cap\{z: \Im z \ge 0 \}, \\
\phi_U(U\cap\partial S) = (-1,1).
\end{cases}

A simple arc in a surface S is an image of a homeomorphism of the interval [0,1] to the surface. An embedding of a graph G(V,E) to a surface S is a representation of the vertices V of the graph by distinct points of S, w/the boundary of the graph on the boundary of the surface and the edges E by the simple non-intersecting and non-touching simple arcs connecting corresponding endpoints.

For a graph G embedded in a surface S the connected components of S\E are called faces. The embedding is proper if the faces are simply connected, except possibly the unbounded infinite one. The embedded graph G* is called dual to graph G if its vertices are located in distinct (and all) faces of graph G and vice versa, and its edges connect vertices w/corresponding adjacent faces. The edges of the graph G and its dual G* are in the 1-to-1 correspondence. The embedded graph and its dual can be unified in a single construction of the medial graph M(G) defined later in the book. It will be clear from the context how to slightly modify the definitions for graphs w/boundary.

A graph that can be embedded in the plane or the sphere is called planar graph.