外平面グラフ

グラフ理論において、外平面グラフとは、すべての頂点が図の外側の面に属する 平面図を持つグラフです。

外平面グラフは、（平面グラフに対するワグナーの定理と同様に）2 つの禁制小数 K ₄とK _2,3、またはコリン・ド・ヴェルディエールグラフ不変量によって特徴付けられる。外平面グラフは、2 連結である場合にのみハミルトン閉路を持ち、その場合、外面は一意のハミルトン閉路を形成する。すべての外平面グラフは 3 色可能であり、退化とツリー幅は最大で 2 である。

外平面グラフは、平面グラフ、直列並列グラフのサブグラフ、円グラフのサブセットです。外平面性を維持しながらそれ以上の辺を追加できない最大外平面グラフは、弦グラフや可視グラフでもあります。

外平面グラフは、完全マッチングを使用して基本グラフの 2 つのコピーを接続することによって形成されるグラフの平面性を決定する問題に関連して、Chartrand と Harary (1967) によって最初に研究され、命名されました(たとえば、一般化されたピーターセン グラフの多くは、サイクル グラフの 2 つのコピーからこのように形成されます)。彼らが示したように、基本グラフが 2 重連結である場合、このように構築されたグラフが平面であるためには、基本グラフが外平面であり、マッチングが外部サイクルの二面体順列を形成する必要があります。Chartrand と Harary は、外平面グラフに対するクラトフスキーの定理の類似物も証明しました。つまり、グラフが外平面であるためには、 2 つのグラフK ₄またはK _{2,3のいずれかの}細分が含まれないということになります。

外平面グラフは、平面上に交差なく描画できる無向グラフであり、すべての頂点が描画の境界のない面に属する。つまり、どの頂点も辺に完全に囲まれていない。あるいは、グラフGに新しい頂点を追加し、その頂点を他のすべての頂点に接続する辺で形成したグラフが平面グラフである場合、グラフG は外平面グラフである。^{[1] [2]}

最大外平面グラフは、外平面性を維持しながら追加の辺を追加できない外平面グラフです。n 頂点を持つすべての最大外平面グラフには、ちょうど2 n  − 3 の辺があり、最大外平面グラフのすべての境界面は三角形です。

外平面グラフには、平面グラフに対するクラトフスキーの定理やワグナーの定理に類似した禁制グラフ特性がある。つまり、グラフが外平面グラフであるためには、完全グラフK ₄または完全二部グラフK _2,3の細分を含まないことが必要である。^[3]あるいは、グラフが外平面グラフであるためには、K ₄またはK _{2,3 を}マイナーグラフ（辺を削除して縮小することで得られるグラフ）として含まないことが必要である。^[4]

三角形のないグラフが外平面グラフであるとは、 K _2,3の細分を含まない場合のみである。^[5]

グラフが外平面グラフであるためには、そのColin de Verdière グラフ不変量が最大で 2 である必要があります。同様に Colin de Verdière 不変量が最大で 1、3、または 4 であることによって特徴付けられるグラフは、それぞれ線形フォレスト、平面グラフ、および リンクなしで埋め込み可能なグラフです。

外平面グラフが2重連結であるためには、グラフの外面が頂点の重複のない単純な閉路を形成する必要がある。外平面グラフがハミルトンであるためには、2重連結である必要がある。この場合、外面は唯一のハミルトン閉路を形成する。^{[6]より一般的には、外平面グラフの最長閉路のサイズは、その最大の2重}連結成分の頂点数と同じである。このため、外平面グラフのハミルトン閉路と最長閉路を見つけることは、任意のグラフに対するこれらの問題のNP完全性とは対照的に、線形時間で解決できる可能性がある。

すべての極大外平面グラフはハミルトン性よりも強い条件を満たします。つまり、ノードパンサイクリックであり、 3からグラフの頂点数までの範囲のすべての頂点vとすべてのkに対して、 v を含む長さkのサイクルがあります。この長さのサイクルは、残りのグラフの外面の長さが k になるまで、削除された頂点がvではない単一の辺でグラフの残りの部分に接続されている三角形を繰り返し削除することによって見つけることができます。 [ ^7]

平面グラフが外平面グラフとなるのは、その2連結成分のそれぞれが外平面グラフである場合に限ります。^[5]

ループのない外平面グラフはすべて、3色のみで色付けできる。 ^{[8]この事実は、フィスク (1978) による}Chvátal の アートギャラリー定理の簡略化された証明で顕著に表れている。3色塗りは、次数が2以下の頂点をすべて削除し、残りのグラフを再帰的に色付けし、削除した頂点をその2つの隣接頂点とは異なる色で追加するという貪欲な色付けアルゴリズムによって線形時間で見つけることができる。

ヴィジングの定理によれば、グラフの彩度指数（隣接する2辺が同じ色にならないように辺を彩色するために必要な最小の色数）は、グラフの任意の頂点の最大次数か、最大次数に1を加えた値のいずれかである。ただし、連結された外平面グラフでは、グラフが奇数長のサイクルを形成する場合を除き、彩度指数は最大次数に等しい。 ^[9]最適な色数による辺彩色は、弱双対木の幅優先探索に基づいて線形時間で見つけることができる。 ^[8]

外平面グラフの退化は最大で2である。外平面グラフのすべてのサブグラフには、次数が最大で2の頂点が含まれる。^[10]

外平面グラフのツリー幅は最大2であり、これは入力が外平面グラフである場合、任意のグラフに対してNP完全である多くのグラフ最適化問題が動的計画法によって多項式時間で解ける可能性があることを意味する。より一般的には、k外平面グラフのツリー幅はO( k )である。^[11]

すべての外平面グラフは平面内の軸に沿った長方形の交差グラフとして表現できるため、外平面グラフの箱型性は最大で2つです。^[12]

すべての外平面グラフは平面グラフである。すべての外平面グラフは直列並列グラフのサブグラフでもある。^[13]しかし、すべての平面直列並列グラフが外平面であるわけではない。完全二部グラフ K _2,3は平面かつ直列並列であるが、外平面ではない。一方、完全グラフ K ₄は平面であるが、直列並列でも外平面でもない。すべての森グラフとすべてのサボテングラフは外平面である。^[14]

埋め込まれた外平面グラフの弱い平面双対グラフ（埋め込みのすべての境界面に対して頂点を持ち、隣接する境界面のすべてのペアに対して辺を持つグラフ）はフォレストであり、Halinグラフの弱い平面双対は外平面グラフである。平面グラフが外平面グラフであるためには、その弱い双対がフォレストである必要があり、その弱い双対が2連結かつ外平面グラフである場合に限り、Halinグラフである。^[15]

外平面度の概念がある。グラフの1外平面埋め込みは外平面埋め込みと同じである。k  > 1の場合、外面の頂点を削除すると(k − 1)外平面埋め込みになる場合、平面埋め込みはk外平面であると言われる。グラフがk外平面埋め込みを 持つ場合、そのグラフはk外平面である。^[16]

外部1 平面グラフは、1 平面グラフと同様に、頂点が円板の境界上にあり、辺ごとに最大 1 つの交差を持つ円板内に描画できます。

すべての極大外平面グラフは弦グラフである。すべての極大外平面グラフは単純多角形の可視グラフである。^{[17]極大外平面グラフは}多角形の三角分割のグラフとしても形成される。これらは2木、直列並列グラフ、弦グラフの例である。

すべての外平面グラフは円グラフであり、円の弦の集合の交差グラフである。 ^[18]

• グラフクラスとその包含に関する情報システムにおける外平面グラフ
• Weisstein、Eric W.「Outplanar Graph」。MathWorld。