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.