双対グラフ
双対グラフは特定の埋め込みに依存するので、平面グラフの双対グラフは、同じ平面グラフが同型でない異なる双対グラフを持つことができるという意味で一意ではない。図では、青いグラフは同型だが、その双対の赤いグラフはそうではない。下の赤いグラフはすべての次数が6未満であるのに対し、上のグラフは次数6の頂点を持つ。(青いグラフの外側の面に対応する)。
Hassler Whitneyは、グラフが3頂点連結の場合、埋め込み、つまり双対グラフは一意であることを示した。Steinitzの定理により、これらのグラフはまさに多面体グラフ、すなわち凸多面体のグラフとなる。平面グラフは、その双対グラフが3頂点接続の場合に限り、3頂点接続になる。より一般的には、平面グラフは、それが3頂点接続平面グラフの細分である場合に限り、固有の埋め込み、したがって固有の双対を有する。完全2部グラフK2,4ように、3頂点接続されていない平面グラフの場合、埋め込みは一意ではないが、埋め込みはすべて同形となる。この場合、すべての双対グラフは同形になる。
異なる埋め込みは異なる双対グラフをもたらす可能性があるため、あるグラフが他のグラフの双対であるかどうかをテストする問題は自明でないアルゴリズム上の問題となる。2重連結グラフについてはSPQRツリーを用いることで、双対どうしの同値関係の正規の形式を構成することができる。しかし、2重連結ではない平面グラフの場合、そのような同値関係は求まらず、相互双対性をテストする問題はNP完全となる。