平面グラフ

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

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

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

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

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

平面性基準

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

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

有限グラフが平面グラフである場合、それは完全グラフ

K

5

または完全二部グラフ

K

3,3

(ユーティリティグラフ)の細分であるサブグラフを含まない。

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

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

有限グラフが平面グラフである場合、それはマイナーグラフとして

K 5

または

K 3,3 を

持ちません。

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

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

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

その他の基準

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

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

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

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

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

プロパティ

オイラーの公式

オイラーの公式によれば、平面グラフに辺の交差がなく、頂点の数を $v 、辺の数を$ $e$ 、面の数を $f$ （辺で囲まれた領域、外側の無限に広い領域を含む）とすると、

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 \leq 2 eです。オイラーの公式を使用すると、$ $v$ $\geq 3$ の場合、これらのグラフがスパースであることが示されます。

e\leq 3v-6.

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

平均度

複数の辺を持つ連結平面グラフは、不等式 $2 e \geq 3 f$ に従う。これは、各面が少なくとも3つの面と辺の連結を持ち、各辺がちょうど2つの連結に寄与するためである。この不等式をオイラーの公式 $v - e + f = 2$ で代数変換することにより、有限平面グラフの平均次数は6未満であることが分かる。平均次数が高いグラフは平面グラフにはなり得ない。

コイングラフ

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

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

平面グラフ密度

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

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

密度は $0 \leq D \leq 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$ $> 2$ の頂点 $v$ 個がある場合、そのグラフには正確に $3$ $v$ $- 6 個$ の辺と $2$ $v$ $- 4$ 個の面があります。

アポロニアンネットワークは、三角形の面を小さな三角形の三つ組に繰り返し分割することで形成される最大平面グラフです。つまり、平面3木です。

絞殺グラフとは、すべての周縁閉路が三角形であるグラフのことである。極大平面グラフ（あるいはより一般的には多面体グラフ）では、周縁閉路は面であるため、極大平面グラフは絞殺されている。絞殺グラフには弦グラフも含まれ、完全グラフと極大平面グラフのクリーク和（辺を削除せずに）によって形成されるグラフと全く同じである。^[7]

外平面グラフ

外平面グラフとは、平面への埋め込みを持つグラフであり、すべての頂点が埋め込みの無限面に属する。すべての外平面グラフは平面グラフであるが、その逆は成り立たない。K $4 は平面グラフであるが外平面グラフではない。クラトフスキーの定理に似た定理は、有限グラフが外平面グラフである場合、かつそのグラフが$ $K 4$ または $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] $n$ $g\cdot n^{-7/2}\cdot \gamma ^{n}\cdot n!$ $\gamma \approx 27.22687$ $g\approx 0.43\times 10^{-5}$

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

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

その他の結果

4色定理は、すべての平面グラフが 4色可能である(つまり、4 部グラフである) ことを述べています。

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

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

平面グラフ分離定理は、 n頂点平面グラフは頂点を除去することで、最大で2 n /3の大きさの2つの部分グラフに分割できることを述べています。結果として、平面グラフのツリー幅と枝幅はO( √n )となります。 $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つのユーティリティ問題、人気のパズル

注記

^ Trudeau, Richard J. (1993) 『グラフ理論入門』（訂正・増補再出版）ニューヨーク：ドーバー出版、p. 64、ISBN 978-0-486-67870-2、 2012 年8 月 8 日に取得。したがって、平面グラフを平らな面に描画すると、エッジの交差がなくなるか、エッジの交差なしで再描画できるようになります。
^ Barthelemy, M. (2017)、「1.5 平面グラフ」、空間ネットワークの形態形成、Springer、p. 6、ISBN 978-3-319-20565-6
^ 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 。
^ Schnyder, W. (1989)、「平面グラフとポセット次元」、Order、5 (4): 323– 343、doi :10.1007/BF00353652、MR 1010382、S2CID 122785359 。
^ Bhasker, Jayaram; Sahni, Sartaj (1988)、「平面三角形グラフの長方形双対を見つけるための線形アルゴリズム」、Algorithmica、3 ( 1–4 ): 247– 278、doi :10.1007/BF01762117、S2CID 2709057 。
^ Hakimi, SL; Schmeichel, EF (1978)、「最大平面グラフの接続性について」、Journal of Graph Theory、2 (4): 307– 314、doi :10.1002/jgt.3190020404、MR 0512801 ; ハキミとシュマイケルは、最大平面グラフの 3 連結性をハスラー・ホイットニーの定理によるものとしている。
^ シーモア, PD; ウィーバー, RW (1984)、「弦グラフの一般化」、グラフ理論ジャーナル、8 (2): 241– 251、doi :10.1002/jgt.3190080206、MR 0742878 。
^ 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
^ 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。
^ 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
^ 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
^ 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
^ 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
^ マクダーミッド、コリン;ステガー、アンジェリカ; ウェルシュ、ドミニク 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
^ 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
^ ドゥイモヴィッチ、ヴィダ;ジョレット、グウェナエル。ミチェク、ピョートル。パット・モーリン;ウエケルト、トルステン。Wood、David R. (2020)、「平面グラフにはキュー番号が制限されている」、Journal of the ACM、67 (4): 22:1–22:38、arXiv : 1904.04791、doi :10.1145/3385731
^ ボーズ、プロセンジット; Dujmović, ヴィダ;ジャヴァルシネ、メエルヌーシュ。モーリン、パット (2020)、平面グラフの漸近的に最適な頂点ランキング、arXiv : 2007.06455
^ Dębski, Michał; Felsner, Stefan; Micek, Piotr; Schröder, Felix (2021)、「中心色彩の改良境界」、Advances in Combinatorics、arXiv : 1907.04586、doi :10.19086/aic.27351、S2CID 195874032
^ 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
^ Wood, DR (2007). グラフ内のクリークの最大数について.グラフと組合せ論, 23 (3), 337–352. https://doi.org/10.1007/s00373-007-0738-8
^ Tutte, WT (1956)、「平面グラフに関する定理」、アメリカ数学会誌、82 : 99–116、doi :10.1090/S0002-9947-1956-0081471-8、JSTOR 1992980、MR 0081471

参考文献

Kuratowski、Kazimierz (1930)、「Sur le problème des courbes gauches en topologie」(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 — ボイヤー・ミルボルド平面性アルゴリズムのリファレンス実装の無料Cソースコード。このアルゴリズムは、組み合わせ平面埋め込み器とクラトフスキー部分グラフ分離器の両方を提供します。無料ライセンスのオープンソースプロジェクトが、辺追加平面性アルゴリズムの最新バージョンを提供しています。
グラフアルゴリズムライブラリとエディターの公開実装 — 平面性テスト、平面性埋め込み、線形時間での Kuratowski サブグラフ表示を含む GPL グラフアルゴリズムライブラリ。
線形時間平面性テスト、埋め込み、Kuratowski サブグラフ分離、直線描画などの平面グラフ用の Boost Graph ライブラリツール。
3つのユーティリティパズルと平面グラフ
NetLogo Planarity モデル — John Tantalo のゲームの NetLogo バージョン