7.1 Basic definitions

A graph said to be realizable or embeddable on surface S if

-     it is possible to distinguish a collection of n distinct points of S that correspond to the vertices of G and

-     a collection of m curves, pairwise disjoint except possibly for endpoints, on S that correspond to the edges of G

such that if a curve A corresponds to the edge , then only the endpoints of A correspond to vertices of G, namely u and v.

A graph G is a planar graph if it can be drawn in the plane in such a way that no two edges intersect, i.e. if it can be embedded in the plane.

A planar graph G is called maximal planar if, for every pair u, v of non-adjacent vertices of G, the graph is nonplanar.

If a planar graph is embedded in the plane, then it is called a plane graph.

 

 

 

Figure 7.1. Three graphs: is planar but not plane, is planar and plane, is not planar

A region of G is the maximal set of those points which can be connected by a curve A such that any points of A neither corresponds to a vertex of G nor is not a point of an edge of G.

For a plane graph, the boundary of a region R contains all of those points x which correspond to edges or vertices of, and  x can be connected by a curve to any point , where .

Every plane graph G has an unbounded region called the exterior region of G.

A plane graph together with the set of its regions is called a plane map. The faces of a plane map are usually called countries. Two countries are neighbours if their boundaries have an edge in common