Figure 1 (Slightly modified from Wiki)
Duality for Plane Graphs
Prepared by:
Joseph Malkevitch
Department of Mathematics and Computer Studies
York College (CUNY)
Jamaica, New York
email:
malkevitch@york.cuny.edu
web page:
http://york.cuny.edu/~malk/
If G is a plane connected graph, then it is possible to associate another plane graph with G, called the dual of G. The way we can get the dual of G from G is as follows.
Place a single vertex (dot) in each face of G, to represent that face. These will be the vertices of the dual graph. Join two of these vertices with an edge if the faces that they represent share an edge.
The process is illustrated in Figure 1, where the vertices of the original graph have been labeled but those of the dual have not. Note that a dot is placed in the infinite face, and that if a face shares several edges with another face, then the vertices in those two faces are joined for each of the edges involved. The dual, in addition to being a plane graph, inherits a lot of nice properties from the original graph. Many graph theory problems arise from questions like: If plane graph G has property P, will the dual of G also have property P? If not, what special additional properties of G have to be present to make sure that property P holds. If G is the edge-vertex graph of a convex polyhedron in 3-dimensional space, then the dual of G also has this property.
If G' denotes the graph obtained by this geometric process from G, then if we compute the dual of G' we get the original graph back. Note that if G is a graph without loops or multiple edges, then the dual graph may have loops and multiple edges. Two-valent vertices in G will give rise to multiple edges and 1-valent vertices will give rise to 1-gons (loops). However, it is also possible to get a vertex joined to itself in the dual when there is an edge e in G which, when e is removed from the graph (leaving its vertices behind) the result is a graph with more components than G has. An edge such as e is called a bridge of the graph. All the edges in a tree are bridges.
Intuitively, the process of computing a dual of a plane graph "reverses" the roles of vertices and faces. The vertices of G correspond to the faces of the dual, and faces of G correspond to the vertices of the dual. Thus, the vertex valence vector of a graph becomes the face vector of the dual, while the face vector of the original graph becomes the valence vector of the dual The number of edges in a graph and its dual are the same. This is because each edge of the dual arises from some edge in the original graph. Usually, this edge is one that shares a pair of faces in the original graph, but when the edge is a bridge or the edge at a 1-valent vertex in the original graph, there is also exactly one corresponding edge in the dual.
It is important to remember that isomorphic copies of a graph can be embedded in the plane in different ways. Thus, the dual of a graph can depend on the embedding of the graph that is used. This shows up in the fact that plane embeddings of G and H, though they are isomorphic as graphs, might have different face vectors. When this happens, the dual graphs of G and H will not be isomorphic. However, work of the American mathematician Hassler Whitney has clarified the circumstance under which this can happen. If a graph is the edge-vertex graph of a convex polyhedron, this phenomenon does not occur. Steinitz's Theorem tells that a graph G is the vertex edge graph of a convex polyhedron if and only if G is planar and 3-connected.