厚み（グラフ理論）

グラフ理論において、グラフGの厚さとは、 Gの辺を分割できる平面グラフの最小数である。つまり、頂点の集合がすべて同じk 個の平面グラフが存在し、それらの平面グラフの和集合がGとなる場合、 Gの厚さは最大でkである。^{[ 1 ] [ 2 ]}言い換えれば、グラフの厚さとは、和集合がグラフGとなる平面部分グラフの最小数である。^{[ 3 ]}

したがって、平面グラフの厚さは 1 です。厚さ 2 のグラフは双平面グラフと呼ばれます。厚さの概念は、1959 年にゲルハルト・リンゲル^によって提起された双平面グラフの彩色数に関する地球-月問題[ ^{4 ]}と、関連する 1962 年のフランク・ハラリーの予想: 9 つの点上のすべてのグラフまたはその補グラフは非平面で ある。この問題は、完全グラフK ₉が双平面であるかどうかを判定することと同等です(双平面ではないため、予想は正しい)。^{[ 5 ]} 1998 年時点でのこのトピックの現状に関する 包括的な調査^{[ 3 ]}は、ペトラ・ムッツェル、トーマス・オーデンタール、マーク・シャーブロートによって書かれました。^{[ 2 ]}

n個の頂点を持つ完全グラフの厚さKnは_、

${\displaystyle \left\lfloor {\frac {n+7}{6}}\right\rfloor ,}$

ただし、n = 9、10の場合は厚さが 3 となる。^{[ 6 ] [ 7 ]}

いくつかの例外を除いて、完全二部グラフK _a,bの厚さは一般的に次のようになります。^{[ 8 ] [ 9 ]}

${\displaystyle \left\lceil {\frac {ab}{2(a+b-2)}}\right\rceil .}$

すべての森は平面であり、すべての平面グラフは最大で 3 つの森に分割できます。したがって、任意のグラフGの厚さは、同じグラフの樹木数(分割できる森の最小数)と最大で等しく、樹木数を 3 で割った値以上になります。^{[ 2 ] [ 10 ]}

最大次数のグラフ${\displaystyle d}$最大で厚さがあります${\displaystyle \lceil d/2\rceil }$[ ^{11 ]これは}改善できない。${\displaystyle d}$-少なくとも周囲長のある通常のグラフ${\displaystyle 2d}$高い周長により、平面部分グラフは疎になり、その厚さは正確に${\displaystyle \lceil d/2\rceil }$[ ^{12 ]​}

厚さのグラフ${\displaystyle t}$と${\displaystyle n}$頂点は最大で${\displaystyle t(3n-6)}$エッジ。これは平均次数が以下になるためです。${\displaystyle 6t}$彼らの退廃はせいぜい${\displaystyle 6t-1}$そしてそれらの色数は最大で${\displaystyle 6t}$ここで、縮退度は、与えられたグラフのサブグラフの中で、サブグラフ内の最小次数の最大値として定義できます。反対に、グラフが縮退度を持つ場合、${\displaystyle D}$すると、樹木密度と厚さは最大で${\displaystyle D}$グラフの頂点の順序付けを見つけることができ、各頂点は最大で${\displaystyle D}$順序付けでそれより後に来る隣接ノード、そしてこれらのエッジを${\displaystyle D}$異なるサブグラフは、グラフを分割します。${\displaystyle D}$木とは、平面グラフの一種である。

たとえ${\displaystyle t=2}$彩色数の正確な値は不明です。これはゲルハルト・リンゲルの地球・月問題です。トム・スランケの例は、${\displaystyle t=2}$少なくとも9色必要です。^{[ 13 ]}

厚みは同時埋め込みの問題と密接に関係している。^{[ 14 ]} 2 つ以上の平面グラフがすべて同じ頂点集合を共有している場合、エッジを曲線として描画することで、これらのグラフすべてを平面に埋め込むことができ、各頂点はすべての異なる図で同じ位置を持つ。ただし、エッジを直線セグメントとして描画したまま、そのような図を作成することはできないかもしれない。

別のグラフ不変量である、グラフGの直線厚または幾何学的厚は、すべてのグラフが直線エッジで同時に描画できるという制約の下で、G を分解できる最小の平面グラフの数を数えます。ブック厚は、すべての頂点が凸位置に描画され、グラフの円形レイアウトを形成するという追加の制約を加えます。ただし、樹状性および退化の場合とは対照的に、これら 3 つの厚さパラメータのうち、常に定数倍の範囲内にある 2 つはありません。^{[ 15 ]}

与えられたグラフの厚さを計算することはNP困難であり、厚さが最大で2であるかどうかをテストすることはNP完全である。 ^{[ 16 ]}しかし、樹状構造との関連により、厚さを多項式時間で近似比3の範囲内で近似することができる。