Dual Graph

The dual graph $G^*$ of a Polyhedral Graph $G$ has Vertices each of which corresponds to a face of $G$ and each of whose faces corresponds to a Vertex of $G$. Two nodes in $G^*$ are connected by an Edge if the corresponding faces in $G$ have a boundary Edge in common.