外平面グラフ
最大外平面グラフとその3色
完全グラフK 4は、外平面グラフではない最小の平面グラフです。

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

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

外平面グラフは、平面グラフ、直並列グラフの部分グラフ、円グラフのサブセットです。外平面性を保ちながらこれ以上辺を追加できない極大外平面グラフは、弦グラフや可視グラフでもあります。

歴史

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

定義と特徴

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

極大外平面グラフとは、外平面性を保ちながら、追加の辺を追加できない外平面グラフのことである。n頂点を持つすべての極大外平面グラフはちょうど2 n − 3 辺を持ち、 極大外平面グラフのすべての有界面は三角形である。

禁断のグラフ

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

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

コリン・ド・ヴェルディエール不変量

グラフが外平面グラフである場合、そのコリン・ド・ヴェルディエールグラフ不変量は最大2つである。同様にコリン・ド・ヴェルディエール不変量が最大1つ、3つ、または4つであるグラフは、それぞれ線形フォレスト、平面グラフ、および リンクレス埋め込み可能グラフである。

プロパティ

双連結性とハミルトン性

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

あらゆる極大外平面グラフはハミルトン性よりも強い条件を満たす。それはノードパンサイクリックである。つまり、あらゆる頂点vと、 3からグラフの頂点数までの範囲のあらゆるkに対して、 vを含む長さkのサイクルが存在する。この長さのサイクルは、グラフの残りの部分と1辺で接続され、削除された頂点がvではない三角形を繰り返し削除することで見つけることができる。この操作を、残りのグラフの外面の長さがkになるまで繰り返すことで行うことができる。[ 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 4は平面グラフであるが、直列並列でも外平面グラフでもない。全ての森グラフと全てのサボテングラフは外平面グラフである。[ 14 ]

埋め込み外平面グラフ（埋め込みの境界面ごとに頂点を持ち、隣接する境界面のペアごとに辺を持つグラフ）の弱平面双対グラフはフォレストであり、ハリングラフの弱平面双対グラフは外平面グラフである。平面グラフが外平面グラフとなるのは、その弱双対グラフがフォレストである場合のみであり、平面グラフがハリングラフとなるのは、その弱双対グラフが二連結かつ外平面グラフである場合のみである。[ 15 ]

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

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

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

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

注記

  1. ^ウィーガース（1986）
  2. ^フェルスナー（2004年）。
  3. ^チャートランドとハラリー (1967) ;シスロ (1979) ; Brandstädt、Le & Spinrad (1999)、提案 7.3.1、p. 117;フェルスナー (2004)。
  4. ^ディーステル (2000) .
  5. ^ a b Sysło (1979) .
  6. ^チャートランドとハラリー (1967) ;シスロ (1979)。
  7. ^ Li、Corneil、Mendelsohn（2000）、命題2.5。
  8. ^ a b Proskurowski & Sysło (1986)。
  9. ^フィオリーニ（1975年）。
  10. ^リック＆ホワイト（1970年） .
  11. ^ベイカー（1994） .
  12. ^シャイナーマン (1984) ; Brandstädt、Le & Spinrad (1999)、p. 54.
  13. ^ Brandstädt、Le & Spinrad (1999)、p. 174.
  14. ^ Brandstädt、Le & Spinrad (1999)、p. 169.
  15. ^ Sysło & Proskurowski (1983) .
  16. ^ケインとバス (1976) ;シスロ (1979)。
  17. ^エル・ギンディ (1985) ;リンとスキエナ (1995) ; Brandstädt、Le & Spinrad (1999)、定理 4.10.3、p. 65.
  18. ^ヴェッセル＆ペッシェル (1985) ;ウンガー (1988)。

参考文献

「 https://en.wikipedia.org/w/index.php?title=Outerplanar_graph&oldid=1317721911」より取得