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

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

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