交差グラフ

グラフ理論において、交差グラフとは、集合族の交差パターンを表すグラフのことである。あらゆるグラフは交差グラフとして表現できるが、重要な特殊なグラフのクラスは、それらのグラフの交差表現を形成するために使用される集合の種類によって定義される。

正式には、交差グラフGは集合の族から形成される無向グラフである。

${\displaystyle S_{i},\,\,\,i=0,1,2,\dots }$

各集合S _iに対して 1 つの頂点v _iを作成し、対応する 2 つの集合が空でない交差を持つ場合、つまり、 2 つの頂点v _iとv _jをエッジで接続することにより、

${\displaystyle E(G)=\{\{v_{i},v_{j}\}\mid i\neq j,S_{i}\cap S_{j}\neq \emptyset \}.}$

任意の無向グラフG は、交差グラフとして表現できます。Gの各頂点v _iに対して、 v _iに接続する辺からなる集合S _iを作成します。このような集合 2 つが空でない交差を持つのは、対応する頂点が辺を共有する場合に限ります。したがって、 Gは集合S _iの交差グラフです。

Erdős、Goodman 、 Pósa (1966)は、すべての集合S _iを合わせた要素の総数が少なくて済むという意味で、より効率的な構成法を提供しています。この構成法では、集合要素の総数は最大で⁠ n ² / 4 ⁠であり、nはグラフの頂点の数です。彼らは、すべてのグラフが交差グラフであるという観察をSzpilrajn-Marczewski (1945)に帰していますが、 Čulík (1964)も参照するようにと言っています。グラフの交差数とは、グラフの任意の交差表現における要素の総数の最小値です。

多くの重要なグラフ族は、より限定されたタイプの集合族の交差グラフとして記述することができ、例えば、何らかの幾何学的構成から派生した集合などがこれに該当する。

• 区間グラフは、実数直線上の区間の交差グラフ、またはパスグラフの連結部分グラフの交差グラフとして定義されます。
• 無差別グラフは、実数直線上の単位区間の交点グラフとして定義できる。
• 円弧グラフは、円上の弧の交差グラフとして定義されます。
• 多角形円グラフは、円上の頂点を持つ多角形の交点として定義される。
• 弦グラフの特徴の一つは、木の連結した部分グラフの交差グラフとして定義される。
• 台形グラフは、2本の平行線から形成される台形の交点グラフとして定義されます。これらは順列グラフの概念を一般化したものであり、さらに比較可能性グラフの補集合である共比較可能性グラフの特殊なケースです。
• 単位円盤グラフは、平面上の単位円盤の交差グラフとして定義される。
• 円グラフとは、円を構成する弦の集合の交差部分を表すグラフのことである。
• 円充填定理は、平面グラフは、互いに交差しない円で囲まれた平面上の閉円盤の族の交差グラフに正確に等しいと述べている。
• シャイナーマンの予想（現在は定理）によれば、すべての平面グラフは平面上の線分の交点グラフとしても表現できる。しかし、線分の交点グラフは非平面であることもあり、線分の交点グラフを認識することは実数の存在理論にとって完全である（Schaefer 2010 ）。
• グラフGの線グラフは、 Gの辺の交差グラフとして定義され、各辺はその2つの端点の集合として表されます。
• ストリンググラフとは、平面上の曲線の交点グラフのことです。
• グラフがボックス性kを持つとは、次元kの多次元ボックスの交差グラフであって、それより小さい次元のボックスの交差グラフではない場合をいう。
• クリークグラフとは、別のグラフの最大クリークの交差グラフのことである。
• ブロックグラフまたはクリークツリーは、別のグラフの2連結成分の交差グラフである。

シャイナーマン（1985）は、グラフの交差クラス、すなわち、与えられた集合族から抽出された集合の交差グラフとして記述できる有限グラフの族を特徴づけた。この族が以下の性質を持つことが必要かつ十分である。

• グラフ族に含まれるグラフの誘導部分グラフはすべて、そのグラフ族に含まれていなければならない。
• ファミリー内のグラフから頂点をクリークに置き換えることによって形成されるすべてのグラフは、必ずそのファミリーに属していなければならない。
• このグラフ族には無限のグラフ列が存在し、各グラフは列内の次のグラフの誘導部分グラフであり、かつ、このグラフ族のすべてのグラフは列内のいずれかのグラフの誘導部分グラフであるという性質を持つ。

交差グラフ表現において、異なる頂点が異なる集合で表現されなければならないという追加要件がある場合、クリーク拡張特性は省略できる。

交差グラフの順序理論上の類似物は包含順序です。グラフの交差表現が、頂点が隣接するのはそれらの集合が空でない共通部分を持つ場合のみであるような集合で各頂点にラベルを付けるのと同様に、半順序集合の包含表現f は、半順序集合内の任意のxとyに対して、 x  ≤ yとなるのはf ( x ) ⊆ f ( y )の場合のみであるような集合で各要素にラベルを付けます。   

• 接触グラフ

• Čulík, K. (1964)、「グラフ理論の数理論理学および言語学への応用」、グラフ理論とその応用（1963年スモレニツェシンポジウム議事録）、プラハ：チェコスロバキア科学アカデミー出版局、pp. 13–20、MR 0176940  。
• Erdős, Paul ; Goodman, AW; Pósa, Louis (1966)、「集合の交差によるグラフの表現」（PDF）、Canadian Journal of Mathematics、18（1）：106–112、doi：10.4153/CJM-1966-014-3、MR 0186575、S2CID 646660  。
• ゴルンビック、マーティン・チャールズ(1980)、『アルゴリズム的グラフ理論と完全グラフ』、アカデミック・プレス、ISBN 0-12-289260-7。
• McKee, Terry A.; McMorris, FR (1999)、『Topics in Intersection Graph Theory』、SIAM Monographs on Discrete Mathematics and Applications、第2巻 、フィラデルフィア：Society for Industrial and Applied Mathematics、ISBN 0-89871-430-3MR 1672910​ 。
• Szpilrajn-Marczewski、E. (1945)、「Sur deux propriétés des class d'ensembles」、Fund.数学。、33 : 303–307、土井: 10.4064/fm-33-1-303-307、MR 0015448 。
• シェーファー、マーカス（2010）「いくつかの幾何学的および位相的問題の複雑性」（PDF）、グラフ描画、第17回国際シンポジウム、GS 2009、米国イリノイ州シカゴ、2009年9月、改訂論文、Lecture Notes in Computer Science、vol.  5849、Springer-Verlag、pp. 334–344、doi：10.1007/978-3-642-11805-0_32、ISBN  978-3-642-11804-3。
• Scheinerman, Edward R. (1985)、「グラフの交差クラスの特性化」、離散数学、55 (2): 185–193、doi : 10.1016/0012-365X(85)90047-0、MR 0798535 。

• 交差グラフの理論と重要な特殊クラスの交差グラフの概要については、McKee & McMorris (1999)を参照してください。

• Jan Kratochvíl、交差グラフに関するビデオ講義 (2007 年 6 月)
• E. プリスナー著『交差点グラフ郡を巡る旅』