平面性判定

前提知識: 平面グラフ, Kuratowskiの定理, 連結度(グラフ)

与えられたグラフが平面に辺を交差させずに描けるかどうかを判定する問題を平面性判定という。電子回路の配線やグラフの可視化では、まず平面に描けるかを知り、描けるなら実際の描き方を求めたい。Kuratowskiの定理 は、平面に描けないことの証拠が $K_5$ か $K_{3,3}$ の細分という有限の形で必ず見つかることを保証するが、それだけでは効率のよい判定の手順は得られない。
この記事では、判定を小さな部分に分ける帰着（thm-pt-reduction）と、部分グラフの描画からはみ出す部分（ブリッジ）がどの面に入れるかについての必要条件（thm-pt-bridges）を証明する。後者から、閉路に対するブリッジの重なり方で非平面性を示す方法が得られる。これらを使う Demoucron–Malgrange–Pertuiset の算法を紹介し、頂点数に比例する時間で判定できること（Hopcroft–Tarjan、Boyer–Myrvold）を出典とともに述べる。算法の正しさと線形時間の主張は、この記事では証明しない。

問題と証拠

この記事のグラフは有限な単純グラフとし、頂点数を $n$、辺数を $m$ とする。平面への描画・面・平面グラフ図は Kuratowskiの定理 の記事の定義「平面への描画」に従う（辺は折れ線の弧で描く）。

Kuratowskiの定理 の記事の定理「Kuratowski–Wagner の定理」により、平面グラフでないグラフは必ず Kuratowski 部分グラフを含む。描画も Kuratowski 部分グラフも、受け取った側が答えを確かめられる証拠である（BMy04 p. 242）。
判定の最初の段階として、辺の多すぎるグラフをすぐに除ける。

逆は成り立たない。$K_{3,3}$ は $m=9\le12=3n-6$ を満たすが平面グラフでない（平面グラフ の記事の反例の表）。

分割による帰着

Kuratowskiの定理 の記事の「辺を加えられるだけ加えたグラフ」の節と同じく、グラフ $G$ の頂点集合の組 $(V_1,V_2)$ で、$V_1\cup V_2=V(G)$、$A:=V_1\setminus V_2$ と $B:=V_2\setminus V_1$ がともに空でなく、$A$ と $B$ を結ぶ辺がないものを $G$ の分離といい、$S:=V_1\cap V_2$ を分離集合という。$G[V_i]$ は $V_i$ が誘導する部分グラフであり、$G$ の辺はどれも $G[V_1]$ か $G[V_2]$ に属する。$x,y\in V(G)$ について、$G+xy$ は $xy$ が辺でなければ加えたグラフ、辺ならば $G$ 自身を表す。

1 を繰り返し使うと、平面性の判定は連結成分ごと、さらに切断点で分けた 2-連結な部分（ブロック）ごとの判定に帰着する（ブロックについては Die25 §3.1、p. 64）。1 は Die25 Theorem 4.5.1 の証明（p. 112）で Kuratowski の定理から従うと述べられている事実であり、BM76 p. 164 も同じ帰着から算法を始めている。2 を繰り返すと、さらに 3-連結なグラフと三角形の判定に帰着する。実際、各段の $G[V_i]+xy$ は再び 2-連結である。$A,B$ はともに空でないので、$G[V_i]+xy$ は 3 頂点以上で、$G$ より頂点が少ない。$v\in V_i$ を除いたとき、$V_i\setminus\{v\}$ の頂点から $G-v$ の中で $S\setminus\{v\}$ へ向かう道を、$S$ に初めて着くところで切ると、$A$ と $B$ を結ぶ辺がないので $G[V_i]-v$ の中の道になる。$S\setminus\{v\}$ は 1 頂点か、辺 $xy$ で結ばれた 2 頂点なので、$G[V_i]+xy-v$ は連結である。2 の辺 $xy$（仮想辺）は省けない（ex-pt-counterexamples）。3-連結な場合については、Kuratowskiの定理 の記事の補題「3-連結グラフの場合」の証明が、縮約して得た描画に頂点を描き戻すか、描き戻せなければ Kuratowski 部分グラフを見つける手順になっている。

ブリッジとそれが入る面

定義

部分グラフ $H\subset G$ に対し、次のどちらかを $G$ における $H$ のブリッジ（bridge）という。

• $H$ に属さない辺で両端が $H$ の頂点であるもの（両端とともに考える）。これを弦という。
• $G-V(H)$ の連結成分 $D$ に、$D$ と $H$ を結ぶ辺とその $H$ 側の端点を加えた部分グラフ。
  ブリッジ $\beta$ の頂点のうち $H$ に属するものを $\beta$ の付着点といい、その集合を $A(\beta)$ と書く。ブリッジは付着点以外の頂点と辺を共有しない。$G$ の辺で $H$ に属さないものは、ちょうど 1 つのブリッジに属する。ここでの「ブリッジ」は、取り除くと連結成分が増える辺（橋）とは別の概念である。
  閉路 $C$ と、付着点がすべて $C$ の上にある 2 つのブリッジ $\beta_1,\beta_2$ が $C$ に関して重なるとは、次のどちらかが成り立つことをいう。
• (a) $\beta_1$ と $\beta_2$ が 3 個以上の付着点を共有する。
• (b) $a_1,a_2\in A(\beta_1)$ と $b_1,b_2\in A(\beta_2)$ で、4 頂点が相異なり、$C$ の上に $a_1,b_1,a_2,b_2$ の巡回順に並ぶものがある。
  $H$ が 2-連結で描画 $\tilde H$ をもつとき、$\tilde H$ の各面 $f$ の境界は閉路 $C_f$ である（Kuratowskiの定理 の記事の注意「この記事で証明せずに用いる事実」の (F3)）。ブリッジ $\beta$ の付着点がすべて $C_f$ の上にあるとき、$\beta$ は面 $f$ に描けるといい、そのような面の集合を $F(\beta,\tilde H)$ と書く（BM76 p. 164）。

主定理

以下では Kuratowskiの定理 の記事の (F1)–(F4) を用いる。

1 は BM76 Theorem 9.14（p. 164）である。2 は、同じ面に入るブリッジどうしが互いに邪魔をしないことを、重なれば $K_5$ か $K_{3,3}$ が平面に描けてしまうという形で示している。$H$ が閉路のとき、面は内側と外側の 2 つだけなので、次が従う。

重なりグラフが二部グラフであることは平面性の必要条件にすぎない。たとえば $K_5$ の三角形 $C=123$ では、残りの 2 頂点 $4,5$ とそこから出る 7 本の辺が 1 つのブリッジをなし、重なりグラフは 1 頂点で二部グラフだが、$K_5$ は平面グラフでない。

Demoucron–Malgrange–Pertuiset の算法

thm-pt-reduction の 1 により、2-連結なグラフを判定できれば十分である。次の算法は Demoucron・Malgrange・Pertuiset（1964 年）による（BM76 §9.8、pp. 163–169）。$G$ を頂点 3 個以上の 2-連結なグラフとする。

1. $G$ の閉路 $G_1$ を 1 つ選び、多角形として描いた描画 $\tilde G_1$ をとる。$i:=1$ とする。
2. $E(G_i)=E(G)$ なら終了し、$\tilde G_i$ が $G$ の描画である。そうでなければ、$G_i$ のブリッジをすべて求め、各ブリッジ $\beta$ について $F(\beta,\tilde G_i)$ を求める。
3. $F(\beta,\tilde G_i)=\emptyset$ となるブリッジがあれば終了し、$G$ は平面グラフでないと答える。$F(\beta,\tilde G_i)$ がただ 1 つの面 $f$ からなるブリッジがあれば、その $\beta$ と $f$ を選ぶ。なければ、任意のブリッジ $\beta$ と $f\in F(\beta,\tilde G_i)$ を選ぶ。
4. $\beta$ の中で 2 つの付着点を結び、内部が $\beta$ の $G_i$ に属さない部分にある道 $P$ を選ぶ。$P$ を面 $f$ の中に描き（(F4) と同じく、境界の閉路の 2 頂点を面の中を通る弧で結べる）、$G_{i+1}:=G_i\cup P$ とする。$i$ を $1$ 増やして 2 へ戻る。
   $G$ は 2-連結なので、各ブリッジの付着点は 2 個以上あり、4 の道がとれる。$G_i$ は閉路に両端の異なる道を順に加えたものなので 2-連結であり（Die25 Proposition 3.1.1、p. 63）、面の境界は閉路である。各回で辺が 1 本以上増えるので、算法は有限回で止まる。
   2 で止まれば $G$ の描画が得られているので、$G$ は平面グラフである。3 で止まったときの答えが正しいことは、「$G$ が平面グラフなら、各段階の $\tilde G_i$ を含む $G$ の描画がある」ことから従う。実際、そのような描画の $G_i$ への制限は $\tilde G_i$ なので、thm-pt-bridges の 1 によりどのブリッジも描ける面をもち、3 で止まることはない。この性質は、描ける面が 1 つしかないブリッジを優先し、どのブリッジも 2 つ以上の面に描けるときには 2 つの面の共通の境界にだけ付着するブリッジを入れ替えられることを使って帰納法で示される。その概略は BM76 p. 167 にあり、この記事では証明しない。各段階の操作はそれぞれ効率よく行え、算法全体は多項式時間で動くことが知られている（BM76 pp. 167–169。この記事では証明しない）。

BM76 Figure 9.29（p. 165）は平面グラフでの実行例、Figure 9.30（p. 166）は平面グラフでない場合の実行例である。

線形時間の判定

平面性は頂点数 $n$ に比例する時間で判定できる。最初の線形時間の算法は Hopcroft と Tarjan（1974 年）による（BMy04 p. 243）。2-連結なグラフの閉路を描き、残りを閉路の内側か外側に加える道に分けていく方法で、上の算法と同じく道を加えていく発想に立つ。Boyer と Myrvold は、深さ優先探索 の木に沿って辺を 1 本ずつ加えていく算法を与え、$n$ 頂点のグラフの平面性を $O(n)$ 時間で判定できること（BMy04 Theorem 1、p. 259）、平面グラフなら各頂点のまわりの辺の時計回りの順として描画を $O(n)$ 時間で出力できること（Corollary 2、p. 260）を示した。平面グラフでない場合には Kuratowski 部分グラフを取り出す（§8、p. 264 以降）。辺数ではなく頂点数で時間を測れるのは、prop-pt-edge-filter により辺を頂点数の定数倍に制限できるからである（同 p. 242）。これらの主張は、この記事では証明しない。

条件を外したときの反例

補足

• 他の特徴づけ：平面グラフであることは、双対グラフ の記事の注意「Whitney の定理」の抽象的な双対の存在や、閉路空間の基底についての MacLane の条件（Die25 Theorem 4.5.1、p. 112）とも同値である。
• 例：車輪グラフ は 3-連結な平面グラフの基本的な例で、thm-pt-reduction で分けられない。

関連項目

• 前提: 平面グラフ, Kuratowskiの定理, 連結度(グラフ)
• 関連: 双対グラフ, 二部グラフ, 深さ優先探索
• 例: 車輪グラフ, 完全二部グラフ
• 発展: 位相的グラフ理論, 四色定理