平面グラフ

平面グラフ (plane graph) は、平面上の頂点集合とそれを交差なく結ぶ辺集合からなるグラフのことである。平面グラフと同型なグラフのことを平面的グラフ (planar graph) という。

平面的グラフは、球面などの種数0の曲面に描けるグラフと同値である。

極小な非平面的グラフは、K_3,3とK₅。

性質

• Gが平面的グラフならば、|E(G)|≦3|V(G)|-6。ただし、|V(G)|≧3。
• Gが単純グラフで平面的グラフならば、Gは、次数が5以下の頂点を持つ。
• 種数gの曲面S上に描かれた連結グラフGが、Sをf個の領域に分割しているとする。このとき、|V(G)|-|E(G)|+f=2-2gが成り立つ。（オイラーの公式）
• グラフが非平面的であるのは、K_3,3またはK₅と同相な部分グラフを含むとき、かつそのときに限る。（クラトフスキーの定理）
• 平面的グラフの部分グラフは総て平面的グラフである。