平面グラフ

カジミエシュ・クラトフスキは、禁止グラフを用いて平面グラフの特徴付けを行い、これは現在クラトフスキの定理として知られている。

有限グラフは、完全グラフK ₅または完全二部グラフK _3,3 (ユーティリティグラフ)の細分である部分グラフを含まない場合に限り、平面グラフである。

グラフの細分化は、頂点を辺に挿入すること（例えば、辺• —— • を • — • — • に変更すること）によって、0 回以上行われます。

ワグナーの定理は、細分化を考慮する代わりに、小区分を扱う。

有限グラフは、 K ₅またはK _{3,3 を}マイナーとして持たない場合に限り平面グラフである。

グラフのマイナーは、部分グラフを取り出し、辺を頂点に繰り返し縮約することによって得られ、元の端点の各隣接頂点が新しい頂点の隣接頂点になります。

クラウス・ワグナーは、より一般的に、任意のマイナー閉クラスを持つグラフが、有限個の「禁止マイナー」によって決定されるかどうかを問いかけた。これは現在、ロバートソン・シーモアの定理として知られ、一連の論文で証明されている。この定理の言葉で言えば、K ₅とK _3,3は、有限平面グラフのクラスに対する禁止マイナーである。

実際には、クラトフスキーの基準を用いて、与えられたグラフが平面グラフであるかどうかを素早く判定することは困難です。しかし、この問題には高速なアルゴリズムが存在します。n個の頂点を持つグラフの場合、グラフが平面グラフであるかどうかをO ( n ) （線形時間）で判定することが可能です（平面性判定を参照）。

v個の頂点、e個の辺、f個の面を持つ単純な連結平面グラフの場合、 v ≥ 3に対して以下の単純な条件が成り立つ。

• 定理1. e ≤ 3 v − 6 ;
• 定理2. 長さ3のサイクルが存在しない場合、e ≤ 2v − 4が成り立つ。
• 定理3. f ≤ 2 v − 4。

この意味で、平面グラフは疎グラフであり、辺の数はO ( v )個のみで、漸近的に最大値O ( v² )よりも小さい。例えば、グラフK3,3_{は頂点が 6 個、辺が 9 個で、長さ 3 のサイクルはない}^。したがって、定理 2 により、平面グラフにはなり得ない。これらの定理は平面性のための必要条件を提供するが、十分条件ではないため、グラフが平面グラフではないことを証明するためにのみ使用でき、平面グラフであることを証明するためには使用できない。定理 1 と定理 2 の両方が成り立たない場合は、他の方法を使用することもできる。

• ホイットニーの平面性基準は、代数的双対の存在に基づく特徴付けを与える。
• マックレーンの平面性基準は、サイクル空間を介して有限平面グラフの代数的特徴付けを与える。
• フレイセイクス・ローゼンシュティール平面性基準は、深さ優先探索木のコツリーエッジの二分割の存在に基づく特徴付けを与える。これは左右平面性判定アルゴリズムの中心となるものである。
• シュナイダーの定理は、部分順序次元の観点から平面性を特徴づけるものである。
• コリン・ド・ヴェルディエールの平面性基準は、グラフによって定義される特定のシュレーディンガー演算子の2番目の固有値の最大重複度に基づいて特徴付けを与える。
• ハナニ・トゥッテの定理は、グラフが平面グラフであるのは、そのグラフの描画において、各独立な辺のペアが偶数回交差する場合に限ると述べている。この定理は、法 2の方程式系を用いて平面グラフを特徴づけるために使用できる。

オイラーの公式によれば、有限で連結な平面グラフが辺の交差なしに平面上に描かれ、vが頂点の数、eが辺の数、fが面の数 (辺で囲まれた領域、外側の無限に大きな領域を含む) である場合、

${\displaystyle v-e+f=2.}$

例として、上記のバタフライグラフでは、 v = 5、e = 6、f = 3です。一般に、f面のすべての平面グラフに対してこの性質が成り立つ場合、グラフを平面のままにして追加の面を作成するグラフへの変更は、v − e + fを不変に保ちます。この性質はf = 2のすべてのグラフに対して成り立つため、数学的帰納法により、すべての場合に成り立ちます。オイラーの公式は、次のように証明することもできます。グラフが木でない場合、サイクルを完成させるエッジを削除します。これにより、 eとf の両方が1 ずつ減少し、v − e + fは一定のままになります。残りのグラフが木になるまで繰り返します。木ではv = e + 1、f = 1となり、v − e + f = 2、つまりオイラー標数は 2 になります。

有限連結単純平面グラフでは、任意の面（外側の面を除く）は少なくとも 3 つの辺で囲まれ、すべての辺は最大で 2 つの面に接するため、3 f ≤ 2 eとなります。オイラーの公式を用いると、 v ≥ 3の場合、これらのグラフは疎であることがわかります。

${\displaystyle e\leq 3v-6.}$

オイラーの公式は凸多面体にも適用できます。これは偶然ではありません。すべての凸多面体は、多面体の面の中心付近を透視の中心として平面に投影したシュレーゲル図を用いることで、連結した単純平面グラフに変換できます。ただし、すべての平面グラフがこのように凸多面体に対応するわけではありません。例えば、木構造はそうではありません。シュタイニッツの定理によれば、凸多面体から形成される多面体グラフは、まさに有限の3連結単純平面グラフです。より一般的には、オイラーの公式は、凸性に関わらず、面が球面と位相的に等価な表面を形成する単純多角形である任意の多面体に適用されます。

複数の辺を持つ連結平面グラフは、不等式2 e ≥ 3 fを満たします。これは、各面が少なくとも 3 つの面-辺接続を持ち、各辺がちょうど 2 つの接続を持つためです。この不等式をオイラーの公式v − e + f = 2を用いて代数的に変換すると、有限平面グラフの平均次数は厳密に 6 未満であることがわかります。平均次数が 6 を超えるグラフは平面グラフにはなり得ません。

平面上に描かれた2つの円がちょうど1点で交わるとき、それらは接している（または接吻している）と言います。「コイングラフ」とは、内部が重なり合わない円の集合から構成されるグラフで、各円に頂点を、接している円のペアごとに辺を作成します。 1936年にポール・コーベによって初めて証明された円充填定理は、グラフが平面グラフであるのは、それがコイングラフである場合に限ると述べています。

この結果は、すべての単純平面グラフは、その辺が互いに交差しない直線となるように平面に埋め込むことができるというファーリーの定理の簡単な証明となる。グラフの各頂点をコイングラフ表現における対応する円の中心に配置すると、接する円の中心間の線分は他のどの辺とも交差しない。

平面グラフまたはネットワークのメッシュ係数または密度Dは、v個の頂点を持つグラフの場合、境界のある面の数f -1 （ Mac Laneの平面性基準によるグラフの回路ランクと同じ）と、その最大可能値2v - 5の比です。

${\displaystyle D={\frac {f-1}{2v-5}}}$

密度は0 ≤ D ≤ 1を満たし、D = 0は完全に疎な平面グラフ (木) の場合、D = 1 は完全に密な (極大) 平面グラフの場合である。^{[ 3 ]}

辺の交差がない平面への (必ずしも単純ではない) 連結グラフの埋め込みGが与えられたとき、双対グラフG*を次のように構築します。Gの各面(外側の面を含む) から 1 つの頂点を選択し、Gの各辺eに対して、 eで交わるGの 2 つの面に対応するG*の 2 つの頂点を結ぶ新しい辺をG*に導入します。さらに、この辺はe をちょうど 1 回だけ交差し、 GまたはG*の他のどの辺とも交差しないように描画されます。すると、 G*は再び (必ずしも単純ではない) 平面グラフの埋め込みになります。G と同じ数の辺、G の面と同じ数の頂点、G の頂点と同じ数の面を持ちます。「双対」という用語は、 G ** = Gであるという事実によって正当化されます。ここでの等号は、球面上の埋め込みの等価性です。Gが凸多面体に対応する平面グラフである場合、G*は双対多面体に対応する平面グラフです。

双対グラフは、その双対グラフの多くの性質が元のグラフの性質と単純な方法で関連しているため有用であり、双対グラフを調べることでグラフに関する結果を証明することができる。

特定の埋め込みに対して構築された双対は（同型を除いて）一意であるが、グラフは異なる（つまり同相でない）埋め込みから得られる、異なる（つまり同型でない）双対を持つ可能性がある。

単純グラフは、平面グラフであるが、与えられた頂点集合に辺を追加すると、その性質が失われる場合に、極大平面グラフと呼ばれます。この場合、すべての面（外側の面を含む）は 3 つの辺で囲まれ、平面三角形分割という別の用語が説明されます（厳密には、これはグラフの平面描画を意味します）。「三角形グラフ」^{[ 4 ]}または「三角形グラフ」^{[ 5 ]}という別の名称も使用されていますが、これらはそれぞれ完全グラフの線グラフと弦グラフを指すことが多いため、曖昧です。3 個を超える頂点を持つすべての極大平面グラフは、少なくとも 3 連結です。^{[ 6 ]}

極大平面グラフがv個の頂点を持ち、 v > 2である場合、そのグラフは正確に3 v − 6 個の辺と2 v − 4個の面を持つ。

アポロニウスネットワークとは、三角形の面を小さな三角形の3つ組に繰り返し分割することによって形成される、最大の平面グラフのことである。言い換えれば、平面3次元木である。

絞殺グラフとは、すべての周辺サイクルが三角形であるグラフのことである。最大平面グラフ（またはより一般的には多面体グラフ）では、周辺サイクルは面であるため、最大平面グラフは絞殺グラフである。絞殺グラフには弦グラフも含まれ、完全グラフと最大平面グラフのクリーク和（エッジを削除しない）によって形成できるグラフと全く同じである。^{[ 7 ]}

外平面グラフとは、平面への埋め込みを持ち、すべての頂点が埋め込みの無限面に属するグラフのことである。すべての外平面グラフは平面グラフであるが、その逆は成り立たない。K _{4は平面グラフであるが、外平面グラフではない。クラトフスキーの定理に類似した定理によれば、有限グラフが外平面グラフであるのは、それが}K ₄またはK _2,3の細分を含まない場合に限る。上記は、グラフGに新しい頂点を追加し、それを他のすべての頂点に辺で接続して形成されるグラフが平面グラフである場合、グラフGが外平面グラフであるという事実の直接的な帰結である。^{[ 8 ]}

グラフの 1-外平面埋め込みは、外平面埋め込みと同じです。k > 1の場合、平面埋め込みは、外側の面の頂点を取り除くと( k -1) -外平面埋め込みになる場合、 k-外平面です。グラフは、k-外平面埋め込みを持つ場合、k-外平面です。

ハリングラフは、次数が2のノードを持たない無向平面木から、その葉を平面埋め込みによって与えられた順序でサイクルに接続することによって形成されるグラフです。言い換えれば、 1つの面が他のすべての面に隣接している多面体グラフです。すべてのハリングラフは平面です。外平面グラフと同様に、ハリングラフは木幅が小さいため、制約のない平面グラフよりも、ハリングラフ上の多くのアルゴリズムの問​​題が簡単に解決できます。^{[ 9 ]}

上向き平面グラフとは、辺が交差しない曲線で、かつ常に上向きに配向された有向非巡回グラフのことである。すべての平面有向非巡回グラフが上向き平面グラフであるとは限らず、与えられたグラフが上向き平面グラフであるかどうかを判定することはNP完全問題である。

平面グラフは、そのすべての面（外側の面を含む）が凸多角形である場合に凸であると言われます。すべての平面グラフが凸埋め込みを持つわけではありません（例えば、完全二部グラフK _2,4など）。グラフが凸に描画できる十分条件は、それが3 頂点連結平面グラフの細分であることです。タットのバネ定理は、単純な 3 頂点連結平面グラフの場合、内側の頂点の位置をその隣接頂点の平均として選択できることさえ述べています。

単語で表現可能な平面グラフには、三角形を含まない平面グラフ、より一般的には3色で彩色可能な平面グラフ^{[ 10 ]}、三角形グリッドグラフの特定の面分割^{[ 11 ]}、グリッドで覆われた円筒グラフの特定の三角形分割^{[ 12 ]などが含まれます。}

（ラベル付き）平面グラフの数の漸近値${\displaystyle n}$頂点は${\displaystyle g\cdot n^{-7/2}\cdot \gamma ^{n}\cdot n!}$、 どこ${\displaystyle \gamma \approx 27.22687}$そして${\displaystyle g\approx 0.43\times 10^{-5}}$[ ^{13 ]​}

ほぼすべての平面グラフは指数関数的な数の自己同型写像​​を持つ。^{[ 14 ]}

ラベルなし（非同型）平面グラフの数${\displaystyle n}$頂点は$27.2^n$そして$30.06^n$[ ^{15 ]​}

四色定理とは、すべての平面グラフは4色で彩色可能である（すなわち、4分割可能である）という定理である。

ファーリーの定理は、すべての単純平面グラフは平面直線グラフとして表現できると述べています。普遍点集合とは、 n個の頂点を持つすべての平面グラフが、その点集合のすべての頂点を含む埋め込みを持つような点の集合です。整数格子の長方形部分集合を取ることによって形成される、2 乗サイズの普遍点集合が存在します。すべての単純外平面グラフは、すべての頂点が固定された円上にあり、すべての辺が円盤の内側にあり交差しない直線セグメントであるような平面への埋め込みを許容するため、n個の頂点を持つ正多角形は外平面グラフの普遍となります。

シャイナーマンの予想（現在は定理）は、すべての平面グラフは平面上の線分の交点グラフとして表現できると述べている。

平面分離定理は、n個の頂点を持つ平面グラフは、頂点の除去によって最大 2 n /3 のサイズの 2 つのサブグラフに分割できると述べています。${\displaystyle O({\sqrt {n}})}$頂点。結果として、平面グラフにも木幅と枝幅が存在する。${\displaystyle O({\sqrt {n}})}$。

平面積構造定理は、すべての平面グラフは、木幅が最大 8 のグラフとパスの強グラフ積の部分グラフであると述べている。 ^{[ 16 ]}この結果は、平面グラフが有界キュー数、有界非反復彩色数、およびほぼ線形サイズのユニバーサルグラフを持つ ことを示すために使用されてきた。また、平面グラフの頂点ランキング^{[ 17 ]} およびp中心彩色^{[ 18 ]}にも応用されている 。

v個の頂点を持つ 2 つの平面グラフの場合、それらが同型であるかどうかを O( v ) の時間で判定することが可能です(グラフ同型性問題も参照)。^{[ 19 ]}

n個のノードを持つ任意の平面グラフは最大で8(n-2)個の最大クリークを持ち、^{[ 20 ]}これは平面グラフのクラスがクリークの少ないクラスであることを意味します。

ハミルトン閉路に関するタットの定理によれば、すべての4頂点連結平面グラフはハミルトン閉路を持つ。^{[ 21 ]}