On 2D Inverse Problems/Graphs and surfaces

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\geq 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.