グラフが平面的であることの必要十分条件一覧

グラフ$G$を考える.
単射 $\phi:\,V\to\mathbb{R}^2$ 及びジョルダン曲線の族 $(J_e)_{e\in E}$ が存在し, 次の性質を満たすとき, $G$ は平面的であると定義します. 特に$G$が平面的グラフであるとき, 組 $(\phi,(J_e)_{e\in E})$を$G$の埋め込みと呼びます.

性質:
$G$ の各辺 $e=\{u,v\}\in E$に対し,

• $J_e$ は 点 $\phi(u)$ と点 $\phi(v)$ を結ぶ.
• $J_e\backslash \{\phi(u),\,\phi(v)\} \cap \left(\bigcup_{v\in V} \{\phi(v)\} \cup \bigcup_{f \in E\backslash \{e\}} J_f\right)=\emptyset$

$J\subseteq \mathbb{R}^2$ がジョルダン曲線であるとは, 適当な連続な単射 $f:[0,1]\to\mathbb{R}^2$の像として$J$が表せることを指します.

ちなみに, いわゆる「平面グラフ」という言葉は「平面に埋め込まれた」グラフを指すのであって「平面に埋め込める」グラフは指しません.

以下は全て同値です:

• グラフ$G=(V,E)$が平面的である.
• $G$は単純なサイクル基底 (任意の辺$e\in E$に対して$e$を含む閉路が高々2つであるようなサイクル基底)を持つ (MacLaneの定理).
• $K_5$ 及び $K_{3,3}$ をマイナーとして含まない (Wagnerの定理).
• $K_5$ 及び $K_{3,3}$ を位相的マイナーとして含まない (Kuratowskiの定理).
• ある$k\in\mathbb{N}$が存在して, $G$の禁止マイナー $\mathrm{Forb}(G)$ ($G$をマイナーとして含まないような有限グラフの全体)に属する任意のグラフは木幅が高々$k$である (Seymour).
• $G$に対応するグラフ的マトロイド$M$の双対マトロイド$M^{*}$をとったとき, これが別のグラフ$G^{*}$に対応するグラフ的マトロイドとなる (このとき$G^*$は平面的グラフの双対グラフになっている).
• 抽象的双対を持つ.

他にもめっちゃ色々あったはず (学んだら追加していく).