双対グラフ
双対性の概念は、平面以外の二次元多様体上の埋め込みに拡張することができる。ほとんどの場合、埋め込みは各面が位相円板であるという性質を持つ場合に制限されている。この制約は、グラフが接続されているという平面グラフの要件を一般化したものである。この制約により、任意の埋め込みグラフは、同じ曲面に自然に埋め込まれることができる。例えば、完全グラフK7の双対グラフはヒーウッドグラフである。
平面グラフも非平面埋め込みを持つことがあり、その場合の双対は平面双対とは異なる。たとえば、立方体の4つのペトリー多角形(立方体の2つの対向する頂点を削除することによって形成された六角形)は、トーラスに立方体を埋め込むときの六角形の面を形成する。この埋め込みの双対グラフは、二重エッジを持つ完全なグラフK4を形成する4つの頂点を持つ。この双対グラフのトーラス埋め込みでは、各頂点が持つ6つの辺は、その頂点の周囲を巡回する順序で、他の3つの頂点を2回巡回する。平面内の状況とは対照的に、この立方体とその双対の埋め込みは一意ではない。立方体グラフの双対は、他のいくつかのトーラス埋め込みを持つ。
平面グラフの主グラフと双対グラフの性質の間の等価性の多くは、非平面埋め込みの場合に一般化できないか、追加の注意を必要とする。
表面埋め込みグラフに対するもう1つの操作はPetrie双対である 。これは、埋め込みのPetrieポリゴンを新しい埋め込みの面として使用する。このグラフは通常の双対グラフとは異なり、元のグラフと同じ頂点を持つが、一般に異なる面に属する。面双対性とPetrie双対性は6つのウィルソン演算のうちの2つであり、これらの演算による群を生成する。
平面グラフGがTutte多項式TG(x,y)を持つ場合、その双対グラフのTutte多項式はxとy交換することによって得られる。このため、Tutte多項式がGの特定の構造に関する情報を持つ場合、Tutte多項式の引数を交換すると、Gの双対についてそれに対応する情報が得られる。例えば、Gの強い配向の数はTG(0,2)あり、非閉路配向の数はTG(2,0) である。ブリッジレス平面グラフの場合、k色のグラフの色付けは剰余kのゼロフローに対応する。4色定理は、すべてのブリッジレス平面グラフの双対は全て剰余4のゼロフローがあることと同等である。k色付けの数はTutte多項式の値TG(1 − k,0)によって数えられ、その双対である剰余kのゼロフローの数はTG(0,1 − k)によって数えられる。
st-平面グラフとは双極配向をもつグラフである。双極配向とは、一対のソースとシンクによる、循環なしの方向付けで、ソースとシンクが同一の面に属しているようなものである。このようなグラフは、ソースとシンクを結ぶもう一つの辺を加えることで強い結合をもつグラフにすることができる。この補完されたグラフの双対はそれ自身、別のst-平面グラフの補完となる。