平面グラフ

グラフの例
平面グラフ	非平面グラフ
バタフライグラフ	完全グラフK 5
完全グラフK 4	ユーティリティグラフK 3,3

グラフ理論において、平面グラフは平面に埋め込むことができるグラフ、すなわち、平面上に辺が端点でのみ交差するように描くことができるグラフである。言い換えれば、辺が互いに交差しないように描くことができる。^{[ 1 ] [ 2 ]} このような描画は平面グラフ、またはグラフの平面埋め込みと呼ばれる。平面グラフは、各ノードから平面上の点、および各エッジからその平面上の平面曲線へのマッピングを持つ平面グラフとして定義でき、各曲線の端点はその端ノードからマッピングされた点であり、すべての曲線は端点を除いて互いに素である。

平面上に描くことができるすべてのグラフは、立体投影によって球面上にも描くことができ、その逆も同様です。

平面グラフは、組み合わせマップまたは回転システムによってエンコードできます。

球面上の位相的に同値な描画の同値類は、通常、地峡部が存在しないなどの追加の仮定を伴い、平面写像と呼ばれる。平面グラフは外面、すなわち無限面を持つが、平面写像の面はいずれも特別な地位を持たない。

平面グラフは、与えられた種数の曲面上に描画可能なグラフに一般化されます。この用語では、平面グラフは種数 0 を持ちます。これは、平面（および球面）が種数 0 の曲面であるためです。その他の関連トピックについては、 「グラフ埋め込み」を参照してください。

平面性基準

クラトフスキーの定理とワグナーの定理

クラトフスキーの定理またはワグナーの定理を用いて、 K ₅（上）またはK _3,3（下）の部分グラフを見つけることで、超立方体グラフが非平面であることを言葉なしで証明する

カジミエシュ・クラトフスキは、平面グラフを禁制グラフの観点から特徴づけ、現在ではクラトフスキの定理として知られています。

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

グラフの細分化は、エッジに頂点を0 回以上 挿入することによって発生します (たとえば、エッジ• —— • を • — • — • に変更します) 。

K ₅またはK _3,3サブグラフを持たないグラフの例。ただし、 K _3,3の細分が含まれているため、非平面グラフです。

ワーグナーの定理は、細分を考慮する代わりに、マイナーを扱います。

有限グラフが平面グラフである場合、それはマイナーグラフとしてK ₅またはK _{3,3 を}持ちません。

グラフのマイナーは、サブグラフを取得し、エッジを頂点に繰り返し縮小することで生成されます。元の端点の各隣接頂点は、新しい頂点の隣接頂点になります。

ピーターセングラフがK _3,3グラフと同型なマイナーグラフを含み、したがって非平面グラフであることを示すアニメーション

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

その他の基準

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

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

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

この意味で、平面グラフはO ( v )個の辺しか持たない疎グラフであり、最大値O ( v ² )よりも漸近的に小さい。例えば、グラフK _3,3は6つの頂点と9つの辺を持ち、長さ3の閉路は存在しない。したがって、定理2により、このグラフは平面グラフではない。これらの定理は平面性のための必要条件を規定しているが、十分条件ではないため、グラフが平面グラフではないことを証明するためにのみ使用できるが、平面グラフであることを証明するためには使用できない。定理1と定理2の両方が成立しない場合は、他の方法が使用される。

• ホイットニーの平面性基準は代数的双対の存在に基づいた特徴付けを与える。
• Mac Lane の平面性基準は、サイクル空間を介して有限平面グラフの代数的な特徴付けを与えます。
• フライセイクス・ローゼンシュティールの平面性基準は、深さ優先探索木の共木辺の二分法の存在に基づく特徴付けを与える。これは左右平面性検査アルゴリズムの中核を成す。
• シュナイダーの定理は、半順序次元の観点から平面性の特徴付けを与える。
• コリン・ド・ヴェルディエールの平面性基準は、グラフによって定義される特定のシュレーディンガー演算子の 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未満であることが分かる。平均次数が高いグラフは平面グラフにはなり得ない。

コイングラフ

5頂点から1辺を除いた完全グラフ（K ⁻ _5）における円充填定理の例

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

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

平面グラフ密度

平面グラフ、またはネットワークのメッシュ係数または密度Dは、v個の頂点を持つグラフの場合、境界面の数f − 1 （マクレーンの平面性基準によるグラフの回路ランクと同じ）とその最大値2 v − 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つの辺で囲まれています

単純グラフが平面的であるにもかかわらず、（与えられた頂点集合に）任意の辺を追加するとその性質が失われる場合、そのグラフは最大平面グラフと呼ばれます。この場合、すべての面（外側の面も含む）は3本の辺で囲まれます。これは、平面三角形分割（技術的にはグラフの平面描画を意味します）という別名で呼ばれることもあります。「三角形グラフ」 ^{[ 4 ]}や「三角形化グラフ」^{[ 5 ]}という別名も使われてきましたが、これらは曖昧であり、それぞれ完全グラフの線グラフや弦グラフを指すことが多いです。3つ以上の頂点を持つすべての最大平面グラフは、少なくとも3連結です。^{[ 6 ]}

最大平面グラフにv > 2の頂点v個がある場合、そのグラフには正確に3 v − 6 個の辺と2 v − 4個の面があります。

アポロニアンネットワークは、三角形の面を小さな三角形の三つ組に繰り返し分割することで形成される最大平面グラフです。つまり、平面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 ]が含まれます}

定理

平面グラフの列挙

頂点上の（ラベル付き）平面グラフの数の漸近線は であり、ここでである。^{[ 13 ]} ${\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}}$

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

頂点上のラベルなし（非同型）平面グラフの数は～である。^{[ 15 ]} ${\displaystyle n}$ ${\displaystyle 27.2^{n}}$ ${\displaystyle 30.06^{n}}$

その他の結果

四色定理は、すべての平面グラフは4色可能（つまり、4部グラフ） であると述べています

ファリーの定理によれば、すべての単純平面グラフは平面直線グラフとして表現できる。普遍点集合とは、 n頂点を持つすべての平面グラフが、そのすべての頂点を点集合に埋め込むような点の集合である。整数格子の長方形部分集合をとることで形成される、2 乗の大きさの普遍点集合も存在する。すべての単純外平面グラフは、すべての頂点が固定円上にあり、すべての辺が円の内側にあり交差しない直線分であるような平面への埋め込みが可能である。そのため、n頂点の正多角形は外平面グラフに対して普遍的である。

シャイネルマンの予想（現在は定理）は、あらゆる平面グラフは平面上の 線分の交差グラフとして表すことができるというものです。

平面グラフ分離定理は、 n頂点平面グラフは頂点を除去することで、最大で2 n /3の大きさの2つの部分グラフに分割できることを述べています。結果として、平面グラフのツリー幅と枝幅はO( √n )となります。 ${\displaystyle O({\sqrt {n}})}$

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

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

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

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

一般化

頂点グラフとは、1つの頂点を削除することで平面グラフにできるグラフであり、k頂点グラフとは、最大k個の頂点 を削除することで平面グラフにできるグラフです

1平面グラフは、辺ごとに最大 1 つの単純な交差を持つ平面に描画できるグラフであり、k平面グラフは、辺ごと に最大k の単純な交差を持つ平面に描画できるグラフです。

マップグラフとは、平面上の有限個の単連結で内部が互いに素な領域の集合から、少なくとも1つの境界点を共有する2つの領域を接続することで形成されるグラフです。最大3つの領域が1点で接する場合は平面グラフになりますが、4つ以上の領域が1点で接する場合は非平面グラフになる可能性があります（例えば、円を扇形に分割し、扇形を領域とした場合、対応するマップグラフは完全グラフになります。これは、すべての扇形が共通の境界点、つまり中心点を持つためです）。

トーラスグラフとは、トーラス上に交差なく埋め込むことができるグラフです。より一般的には、グラフの種数とは、そのグラフを埋め込むことができる2次元面の最小の種数です。平面グラフの種数は0、非平面トーラスグラフの種数は1です。すべてのグラフは、何らかの（向き付け可能で連結な）2次元閉面（ハンドル付き球面）に交差なく埋め込むことができるため、グラフの種数は明確に定義されます。明らかに、グラフが種数gの（向き付け可能で連結な）面に交差なく埋め込むことができる場合、そのグラフは、それより大きいか等しい種数を持つすべての（向き付け可能で連結な）面に交差なく埋め込むことができます。グラフ理論には、「X種数」（「X」に何らかの修飾語が付く）と呼ばれる他の概念もあります。一般に、これらは上記で定義された修飾語なしの「種数」の概念とは異なります。特に、グラフの非有向性種族（定義で非有向性面を使用）は、一般グラフの場合、そのグラフの種族（定義で有向性面を使用）とは異なります。

あらゆるグラフは、交差することなく三次元空間に埋め込むことができます。実際、二平面構成では、あらゆるグラフを交差なしに描画できます。二平面構成では、二平面が重ねられ、辺はグラフの頂点だけでなく任意の場所で一方の平面からもう一方の平面へ「ジャンプアップ」したり「ドロップダウン」したりできるため、他の辺との交差を回避できます。これは、基板の両面間の電気的接続が可能な両面回路基板を用いて、あらゆる導電体ネットワークを構築できることを意味します（現実世界の一般的な回路基板と同様に、基板の上面の電気接続は配線によって、下面の電気接続は基板自体に構築された銅のトラックによって実現され、基板の両面間の電気接続はドリルで穴を開け、そこに電線を通し、トラックにはんだ付けすることで実現されます）。また、あらゆる道路網を構築するには、橋かトンネルのどちらか一方だけが必要であり、両方は不要であることを意味します（2層で十分であり、3層は不要です）。また、3次元では、交差のないグラフを描くという問題は自明です。しかし、平面グラフの3次元類似物は、リンクなしで埋め込み可能なグラフによって提供されます。これは、2つのサイクルが互いに位相的にリンクされていない方法で3次元空間に埋め込むことができるグラフです。 KratowskiとWagnerによる平面グラフをマイナーとしてK ₅またはK _{3,3を含まないグラフとして特徴付けたのと同様に、リンクなしで埋め込み可能なグラフは、}ピーターセンファミリーの7つのグラフのいずれもマイナーとして含まないグラフとして特徴付けることができます。 外部平面グラフと平面グラフを、コリン・ド・ヴェルディエールグラフ不変量が最大で2つまたは3つであるグラフとして特徴付けることと同様に、リンクなしで埋め込み可能なグラフは、コリン・ド・ヴェルディエール不変量が最大で4つであるグラフです。

参照

• 組合せマップ：平面グラフをエンコードできる組合せオブジェクト
• 平面化、交差点のある描画から、各交差点を新しい頂点に置き換えることによって形成される平面グラフ
• 厚さ（グラフ理論）、与えられたグラフの辺を分割できる平面グラフの最小数
• Planarity は、平面グラフを平面に埋め込むことを目的とするパズルコンピュータゲームです。
• Sprouts（ゲーム）は、ゲームプレイの一部として、一定の制約を受ける平面グラフが構築される鉛筆と紙のゲームです。
• 3つのユーティリティ問題、人気のパズル

注記

1. Trudeau, Richard J. (1993) 『グラフ理論入門』（訂正・増補再出版）ニューヨーク：ドーバー出版、p. 64、ISBN 978-0-486-67870-2、 2012年8月8日取得。したがって、平面グラフは、平面上に描画された場合、辺の交差がないか、または辺の交差なしで再描画できます
2. Barthelemy, M. (2017)、「1.5 平面グラフ」、空間ネットワークの形態形成、Springer、p. 6、ISBN 978-3-319-20565-6
3. Buhl, J.; Gautrais, J.; Sole, RV; Kuntz, P.; Valverde, S.; Deneubourg, JL; Theraulaz, G. (2004)、「アリの回廊ネットワークにおける効率性と堅牢性」、European Physical Journal B、42 (1): 123– 129、Bibcode : 2004EPJB...42..123B、doi : 10.1140/epjb/e2004-00364-9、S2CID 14975826 。
4. Schnyder, W. (1989)、「平面グラフとポーズト次元」、Order、5 (4): 323– 343、doi : 10.1007/BF00353652、MR 1010382、S2CID 122785359  。
5. Bhasker, Jayaram; Sahni, Sartaj (1988)、「平面三角形グラフの長方形双対を見つけるための線形アルゴリズム」、Algorithmica、3 ( 1–4 ): 247– 278、doi : 10.1007/BF01762117、S2CID 2709057 。
6. Hakimi, SL; Schmeichel, EF (1978)、「最大平面グラフの接続性について」、Journal of Graph Theory、2 (4): 307– 314、doi : 10.1002/jgt.3190020404、MR 0512801 ; ハキミとシュマイケルは、最大平面グラフの 3 連結性をハスラー・ホイットニーの定理によるものとしている。
7. シーモア, PD; ウィーバー, RW (1984)、「弦グラフの一般化」、グラフ理論ジャーナル、8 (2): 241– 251、doi : 10.1002/jgt.3190080206、MR 0742878 。
8. Felsner, Stefan (2004), "1.4 Outerplanar Graphs and Convex Geometric Graphs", Geometric graphs and arrangements , Advanced Lectures in Mathematics, Friedr. Vieweg & Sohn, Wiesbaden, pp.  6– 7, doi : 10.1007/978-3-322-80303-0_1 , ISBN 3-528-06972-4、MR  2061507
9. Sysło, Maciej M.; Proskurowski, Andrzej (1983)、「Halinグラフについて」、グラフ理論：1981年2月10～13日にポーランドのラグフで開催された会議の議事録、数学の講義ノート、第1018巻、Springer-Verlag、pp.  248～ 256、doi：10.1007/BFb0071635、ISBN 978-3-540-12687-4。
10. Halldórsson, M.; Kitaev, S.; Pyatkin., A. (2016)、「半推移的方向性と単語表現可能なグラフ」(PDF)、Discr. Appl. Math.、201 : 164– 171、doi : 10.1016/j.dam.2015.07.033、S2CID 26796091 
11. Chen, TZQ; Kitaev, S.; Sun, BY (2016)、「三角形グリッドグラフの面分割の単語表現可能性」、Graphs and Combin、32 (5): 1749– 61、arXiv : 1503.08002、doi : 10.1007/s00373-016-1693-z、S2CID 43817300 
12. Chen, TZQ; Kitaev, S.; Sun, BY (2016)、「グリッド被覆円筒グラフの三角形分割の単語表現可能性」、Discr. Appl. Math.、213 : 60– 70、arXiv : 1507.06749、doi : 10.1016/j.dam.2016.05.025、S2CID 26987743 
13. Giménez, Omer; Noy, Marc (2009), 「平面グラフの漸近列挙と極限法則」, Journal of the American Mathematical Society , 22 (2): 309– 329, arXiv : math/0501269 , Bibcode : 2009JAMS...22..309G , doi : 10.1090/s0894-0347-08-00624-3 , S2CID 3353537 
14. マクダーミッド、コリン;ステガー、アンジェリカ; ウェルシュ、ドミニク JA (2005)、「ランダム平面グラフ」、Journal of Combinatorial Theory、シリーズB、93 (2): 187– 205、CiteSeerX 10.1.1.572.857、doi : 10.1016/j.jctb.2004.09.007 
15. Bonichon, N.; Gavoille, C.; Hanusse, N.; Poulalhon, D.; Schaeffer, G. (2006)、「Planar Graphs, via Well-Orderly Maps and Trees」、Graphs and Combinatorics、22 (2): 185– 202、CiteSeerX 10.1.1.106.7456、doi : 10.1007/s00373-006-0647-2、S2CID 22639942  
16. ドゥイモヴィッチ、ヴィダ;ジョレット、グウェナエル。ミチェク、ピョートル。パット・モーリン;ウエケルト、トルステン。Wood、David R. (2020)、「平面グラフにはキュー番号が制限されている」、Journal of the ACM、67 (4): 22:1–22:38、arXiv : 1904.04791、doi : 10.1145/3385731
17. ボーズ、プロセンジット; Dujmović, ヴィダ;ジャヴァルシネ、メヘルヌーシュ。モーリン、パット (2020)、平面グラフの漸近的に最適な頂点ランキング、arXiv : 2007.06455
18. Dębski, Michał; Felsner, Stefan; Micek, Piotr; Schröder, Felix (2021)、「中心色彩の改良境界」、Advances in Combinatorics、arXiv : 1907.04586、doi : 10.19086/aic.27351、S2CID 195874032 
19. Filotti, IS; Mayer, Jack N. (1980)、「固定種数のグラフの同型性を決定する多項式時間アルゴリズム」、第12回ACMコンピューティング理論シンポジウム論文集(PDF)、pp.  236– 243、doi : 10.1145/800141.804671、ISBN 978-0-89791-017-0, S2CID  16345164
20. Wood, DR (2007). グラフ内のクリークの最大数について.グラフと組合せ論, 23 (3), 337–352. https://doi.org/10.1007/s00373-007-0738-8
21. Tutte, WT (1956)、「平面グラフに関する定理」、アメリカ数学会誌、82 : 99–116、doi : 10.1090/S0002-9947-1956-0081471-8、JSTOR 1992980、MR 0081471  

参考文献

• クラトフスキ、カジミエシュ(1930)、「トポロジーにおける左膝の問題」（PDF）、Fundamenta Mathematicae（フランス語）、15 : 271–283、doi : 10.4064/fm-15-1-271-283。
• Wagner, K. (1937)、「Über eine Eigenschaft der ebenen Komplexe」、Mathematische Annalen (ドイツ語)、114 : 570–590、doi : 10.1007/BF01594196、S2CID  123534907。
• Boyer, John M.; Myrvold, Wendy J. (2005)、「最先端：辺の追加による簡略化されたO(n)平面性」（PDF）、Journal of Graph Algorithms and Applications、8 (3): 241– 273、doi : 10.7155/jgaa.00091。
• McKay, Brendan ; Brinkmann, Gunnar,便利な平面グラフ生成器。
• de Fraysseix, H.; Ossona de Mendez, P.; Rosenstiehl, P. (2006)、「トレモー木と平面性」、International Journal of Foundations of Computer Science、17 (5): 1017– 1029、arXiv : math/0610935、doi : 10.1142/S0129054106004248、S2CID  40107560グラフ描画特集号。
• Bader, DA ; Sreshta, S. (2003年10月1日)、「平面性試験のための新しい並列アルゴリズム（技術レポート）」、UNM-ECE技術レポート03-002、2016年3月16日時点のオリジナルからアーカイブ
• フィスク、スティーブ（1978）「Chvátalのウォッチマン定理の簡潔な証明」、Journal of Combinatorial Theory、シリーズB、24（3）：374、doi：10.1016/0095-8956（78）90059-X。

外部リンク

• 辺追加平面性アルゴリズム ソースコード、バージョン 1.0 — Boyer-Myrvold 平面性アルゴリズムのリファレンス実装の無料 C ソースコード。このアルゴリズムは、組み合わせ平面埋め込み器と Kuratowski 部分グラフ分離器の両方を提供します。無料ライセンスのオープンソースプロジェクトが、辺追加平面性アルゴリズムの最新バージョンを提供しています。
• グラフ アルゴリズム ライブラリとエディターの公開実装— 平面性テスト、平面性埋め込み、線形時間での Kuratowski サブグラフ表示を含む GPL グラフ アルゴリズム ライブラリ。
• 線形時間平面性テスト、埋め込み、Kuratowski サブグラフ分離、直線描画などの平面グラフ用の Boost Graph ライブラリ ツール。
• 3つのユーティリティパズルと平面グラフ
• NetLogo Planarity モデル— John Tantalo のゲームの NetLogo バージョン

「 https://en.wikipedia.org/w/index.php?title=Planar_graph&oldid=1327772131#Maximal_planar_graphs」から取得