Dual Graphs

Graph Theory · Axiom Academy

Understanding the dual relationship between faces and vertices in planar graphs Definition: Given a planar graph G with a fixed planar embedding, the dual graph G* is constructed as follows: Place one vertex in each face of G (including the outer/infinite face) For each edge e in G that borders two faces f₁ and f₂ , connect the corresponding vertices in G* with an edge crossing e Watch as we transform a planar graph into its dual by placing vertices in faces and connecting them across shared edges. 2. Constructing the Dual Graph The construction process is systematic: Step 1: Identify all faces in the planar embedding (including the outer face) Step 2: Place a dual vertex in the center of each face Step 3: For each edge in G , draw a dual edge crossing it to connect the vertices in the adjacent faces Step 4: Bridge edges (loops) in G become loops in G* This animation demonstrates the step-by-step construction on a simple planar graph. Dual graphs exhibit several remarkable properties: Double Dual: (G*)* = G for connected planar graphs (taking the dual twice returns the original) Face-Vertex Correspondence: Each face in G becomes a vertex in G* Degree-Face Size: The degree of a vertex in G* equals the number of edges bounding the corresponding face in G Edge Preservation: |E(G)| = |E(G*)| (same number of edges) Euler's Formula Link: |V(G)| - |E(G)| + |F(G)| = |V(G*)| - |E(G*)| + |F(G*)| = 2 Watch as we demonstrate the double dual property: G → G* → (G*)* = G.

This is the written version of the interactive lesson above. See the full Graph Theory course.