Sweet Emotion

The concept of a dual graph (and thus the "transformation" to generate it) is fundamentally defined for planar graphs only. If a graph is not planar, it cannot be drawn on a plane without edges crossing, and therefore it doesn't have well-defined "faces" in the way required to construct a dual.

So, for an "arbitrary graph," the first step of the "transformation" is often an implicit check: Is the graph planar? If not, a dual graph, as typically defined, does not exist.

Let's illustrate the transformation process with a simple example of a planar graph: a square (a cycle graph with 4 vertices, C4).

---

Example: Transforming a Square (C4) into its Dual Graph

1. The Original Planar Graph (G):

Imagine a square drawn on a piece of paper.

• Vertices: Let's label them A, B, C, D in clockwise order.

• Edges: (A,B), (B,C), (C,D), (D,A).

• Faces:

  • F1: The inner region enclosed by the square.

  • F2: The outer (unbounded) region surrounding the square.

      A-----B
      |     |
      | F1  |
      |     |
      D-----C
    (Outer region is F2)

2. The Transformation Steps to Generate the Dual Graph (G*):

Follow these rules to construct G*:

• Step 1: Create a Vertex for Each Face.

  • Place a new vertex v1* inside face F1.

  • Place a new vertex v2* inside face F2. (So, G* will have two vertices: v1* and v2*.)

• Step 2: Create an Edge in G* for Each Edge in G.

  • For every edge in the original graph G, you will draw an edge in G* that connects the two dual vertices corresponding to the faces that share that original edge.

  Let's trace this for our square:

  1. Edge (A,B): This edge is shared by face F1 (inner) and face F2 (outer).

     • Action: Draw an edge in G* connecting v1* and v2*.

  2. Edge (B,C): This edge is also shared by F1 and F2.

     • Action: Draw another edge in G* connecting v1* and v2*.

  3. Edge (C,D): This edge is also shared by F1 and F2.

     • Action: Draw a third edge in G* connecting v1* and v2*.

  4. Edge (D,A): This edge is also shared by F1 and F2.

     • Action: Draw a fourth edge in G* connecting v1* and v2*.

3. The Resulting Dual Graph (G*):

After completing these steps, the dual graph G* will consist of:

• Vertices: v1* and v2*

• Edges: Four parallel edges connecting v1* and v2*.

      v1* ===== v2* (where '=====' represents 4 parallel edges)

This resulting graph is a multigraph (a graph that allows multiple edges between the same pair of vertices).

Summary of the Transformation:

The "transformation" from a planar graph to its dual graph is not a single mathematical function or a new type of graph, but rather a set of rules for constructing a new graph based on the topological features (faces and shared edges) of the original planar embedding. It fundamentally changes what constitutes a "vertex" and an "edge."