ボクシティ

グラフ理論において、ボックス性は1969 年にFred S. Robertsによって導入されたグラフ不変量です。

グラフのボックス性は、与えられたグラフを軸に平行なボックスの交差グラフとして表現できる最小次元です。つまり、グラフの頂点とボックスの集合の間には 1 対 1 の対応関係が存在し、2 つのボックスが交差するのは、対応する頂点を結ぶ辺がある場合のみです。

この図は、6 つの頂点を持つグラフと、このグラフを長方形 (2 次元のボックス) の交差グラフとして表現したものです。このグラフは、より低い次元ではボックスの交差グラフとして表現できないため、ボックス度は 2 です。

ロバーツ (1969) は、2 n頂点の完全グラフから完全マッチングを取り除いて形成される2 n頂点のグラフは、ちょうどn のボックス性を持つことを示した。つまり、分離した頂点の各ペアは、他の各ペアとは異なる次元で分離されたボックスで表す必要がある。このグラフのちょうどn次元のボックス表現は、 n次元ハイパーキューブの2 n面のそれぞれをボックスに厚くすることで見つけることができる。これらの結果から、このグラフはロバーツ グラフと呼ばれているが、^[1]カクテル パーティー グラフとしてよく知られており、トゥラン グラフT (2 n , n )としても理解できる。

グラフの箱型性は、区間グラフの場合に限り、最大で 1です。任意のグラフGの箱型性とは、区間グラフの辺の集合の交差がGとなるような、同じ頂点集合上にある区間グラフの最小の数です。すべての外平面グラフの箱型性は最大で 2 です^[2]。また、すべての平面グラフの箱型性は最大で 3 です^{[3] 。}

二部グラフの箱型度が2の場合、平面上の軸平行線分の交差グラフとして表すことができます。^[4]

Adiga、Bhowmick、Chandran (2011) は、二部グラフGの箱型性が、Gに関連付けられた高さ 2 の部分順序集合の順序次元の因数 2 以内にあることを次のように証明しました。最小要素の集合はGの 1 つの部分集合に対応し、最大要素の集合はGの 2 番目の部分集合に対応し、対応する頂点がG内で隣接している場合、2 つの要素は比較可能です。同様に、高さ 2 の部分順序集合Pの順序次元は、 Pの比較可能性グラフの箱型性の因数 2 以内にあります( P は高さが 2 なので二部です)。

多くのグラフ問題は、有界な箱型性を持つグラフの方が他のグラフよりも効率的に解いたり近似したりできます。たとえば、最大クリーク問題は、有界な箱型性を持つグラフでは多項式時間で解くことができます。^[5]他のいくつかのグラフ問題では、低次元のボックス表現がわかっている場合に効率的な解決策や近似を見つけることができます。^[6]ただし、そのような表現を見つけるのは難しい場合があります。与えられたグラフの箱型性が最大で特定の値Kであるかどうかをテストすることは、 K = 2の場合でもNP 完全です。 ^{[7] Chandran、Francis、Sivadasan (2010) は、任意のグラフを、グラフの}最大次数の対数係数 以内の次元を持つボックスの交差グラフとして表現するためのアルゴリズムについて説明しています。この結果は、グラフの箱型性の上限を提供します。

自然なパラメータでは難しいにもかかわらず、入力グラフの頂点被覆数でパラメータ化されると、ボックス性は固定パラメータで扱いやすくなります。 ^[8]

グラフGグラフにm辺がある場合、次のようになります 。^{[9] [10]}${\displaystyle box(G)=O({\sqrt {m\cdot \log(m)}})}$

グラフGがk退化（）でありn個の頂点を持つ場合、 Gは箱型性を持つ。^[11]${\displaystyle k\geq 2}$${\displaystyle box(G)\leq (k+2)\lceil 2e\log n\rceil }$

グラフG がt頂点上の完全グラフをマイナーとして持たない場合、^[12] t頂点上の完全グラフをマイナーとして持たず、かつ箱型性を持つグラフが存在する。^[13]特に、任意のグラフGは箱型性を持ち、 はGのコリン・ド・ヴェルディエール不変量を表す。 ${\displaystyle box(G)=O(t^{2}\log t)}$${\displaystyle \Omega (t{\sqrt {\log t}})}$${\displaystyle box(G)=O(\mu (G)^{2}\log \mu (G))}$${\displaystyle \mu (G)}$

• 立方体は、超長方形の代わりに軸が平行な超立方体を使用して、箱型体と同じように定義されます。箱型体は、立方体の一般化です。
• 球形度は、箱形度と同じように定義されますが、単位直径の球体で定義されます。