A subgraph consists of a subset of the vertices and a subset of the edges, with the property that for every edge in the subgraph, both its endpoints are in the subgraph. Two graphs G and G' are isomorphic (G@G' ) if there is a onetoone correspondence between the vertices and onetoone correspondence between the edges, which preserves incidence. In other words, if the edge e in G corresponds to the edge e' in G', then the endpoints of e correspond to the endpoints of e'. A graph G is plane if it is drawn in plane (or on the sphere) with no two edges crossing each other, and it is planar if it is isomorphic to a plane graph. By an embedding of a graph G we mean a drawing of G on a certain surface in which the edges do not cross. A nonplanar graph can be always embedded on some surface, other then the plane (or sphere). For example, all polyhedra graphs are planar, and the graphs K_{5} and K_{3,3} are nonplanar. An automorphism of a graph G is any isomorphism mapping G to itself. All automorphisms of a graph G make its automorphism group denoted as Aut(G). An
embedding of a graph may induce a map M: the division of the unbounded
surface on which the graph is embedded into disjoint simplyconnected regions
called faces. A face with two vertices and two edges will be called
a bigonal face (or just bigon). The dual D(M) of a
given map M can be constructed in the following way: in the map M you draw
a vertex of D(M) in the interior of each region of M (including the exterior
region), and you join them by edges, one edge of D(M) crossing each edge
of M. The graph D(M) is called the dual of M. In the case of polyhedra
and their corresponding graphs, you can join up the points in the interior
of adjacent faces of a polyhedron P to obtain the dual polyhedron D(P).
Doing this a second time gets you back to a polyhedron D(D(P)) isomorphic
to P. Different planar embeddings of a planar graph G may give different
dual graphs D(G), so we can have isomorphic graphs with nonisomorphic
duals.
