双対グラフ

平面グラフ $G$ の双対グラフ $G^*$ を次で定める。頂点は $G$ の面である。$G$ の各辺 $e$ に対し、$f_1(e)$ と $f_2(e)$ を結ぶ辺 $e^*$ を 1 本置く。$f_1(e)=f_2(e)$（$e$ が橋）のときは $e^*$ は自己ループになり、2 つの面が複数の辺を共有すれば多重辺になる。辺集合 $F\subseteq E(G)$ に対し $F^*=\{e^*:e\in F\}$ と書く。