Loading article…
グラフ理論の数学分野において、グラフのキュー番号は、スタック番号（本の厚さ）と同様に定義されるグラフ不変量であり、後入れ先出し（スタック）順序の代わりに先入れ先出し（キュー）順序を使用する。
与えられたグラフのキューレイアウトは、グラフの頂点の全順序付けと、エッジを複数の「キュー」に分割することによって定義されます。各キュー内のエッジの集合は、適切にネストされたエッジを避ける必要があります。つまり、 abとcd が同じキュー内の 2 つのエッジである場合、頂点の順序付けでa < c < d < bとなることはあってはなりません。グラフGのキュー数qn( G )は、キューレイアウト内の最小キュー数です。[ 1 ]
同様に、キューレイアウトから、キューデータ構造を使用して単一のキュー内のエッジを処理することができます。これは、頂点をその順序で考慮し、頂点に到達したときに、その頂点が2番目のエンドポイントであるすべてのエッジをデキューし、次に、その頂点が最初のエンドポイントであるすべてのエッジをエンキューすることによって行われます。ネスト条件により、頂点に到達したときに、その頂点が2番目のエンドポイントであるすべてのエッジがデキューできる状態になっていることが保証されます。[ 1 ]キューレイアウトのもう1つの同等の定義は、与えられたグラフを円筒に埋め込むことです。頂点は円筒内の線上に配置され、各エッジは円筒を1周します。同じキューに割り当てられたエッジは互いに交差することはできませんが、異なるキューに属するエッジ間では交差することができます。[ 2 ]
キューのレイアウトは、 Heath & Rosenberg (1992)によって、グラフのブック埋め込みに関する以前の研究との類推により定義されました。ブック埋め込みは、キューの代わりにスタックを使用して同様の方法で定義できます。彼らが指摘したように、これらのレイアウトは、並列キューのシステムを使用した順列のソートに関する以前の研究にも関連しており、VLSI設計や分散アルゴリズムの通信管理におけるアプリケーションによって動機付けられている可能性があります。[ 1 ]
すべての木はキュー番号 1 を持ち、頂点の順序は幅優先探索によって与えられます。[ 3 ]擬似森林とグリッド グラフもキュー番号 1 を持ちます。[ 4 ]外平面グラフのキュー番号は最大 2 です。3-太陽グラフ (各辺が三角形に置き換えられた三角形) は、キュー番号がちょうど 2の外平面グラフの例です。 [ 5 ]直並列グラフのキュー番号は最大 3 ですが、[ 6 ]平面 3-木のキュー番号は最大 5 です。[ 7 ]
バイナリデブルイングラフのキュー番号は 2です。 [ 8 ] d次元ハイパーキューブグラフのキュー番号は最大で[ 9 ]完全グラフK nおよび完全二部グラフK a、bのキュー番号は正確にわかっています。そして それぞれ。[ 10 ]
すべての 1-キュー グラフは平面グラフであり、頂点が平行線 (レベル) 上に配置され、各エッジが 2 つの連続するレベルの頂点を接続するか、またはすべての以前のレベルをループして同じレベルの 2 つの頂点を接続するアーチを形成する「アーチ レベル付き」平面埋め込みを持ちます。逆に、すべてのアーチ レベル付き平面グラフは 1-キュー レイアウトを持ちます。[ 11 ] 1992 年にHeath、Leighton 、 Rosenberg (1992)は、すべての平面グラフはキュー数が制限されていると予想しました。この予想は、2019 年にDujmović ら (2020)によって肯定的に解決され、平面グラフ、より一般的にはすべての適切なマイナー クローズ クラスのグラフはキュー数が制限されていることが示されました。特に、Dujmović らは、 (2020)は平面グラフのキューの数が最大で49であることを証明し、 Bekos、Gronemann 、 Raftopoulou (2021)によってその上限は42に縮小されました。
強いキュー数と呼ばれるキュー数の変形を使用すると、グラフ積のキュー数は、積内の因子のキュー数と強いキュー数の関数によって制限できます。[ 12 ]
キュー番号が小さいグラフは疎グラフです。n個の頂点を持つ1キューグラフは最大で2n-3個のエッジを持ち[ 13 ]、より一般的にはキュー番号qのグラフは最大で2qn-q(2q+1)個のエッジを持ちます[ 14 ]。これは、これらのグラフの彩色数も小さいことを意味します。特に、1キューグラフは3彩色可能であり、キュー番号qのグラフは少なくとも2q+1色、最大で4q色を必要とする場合があります[ 14 ] 。反対に、エッジ数の上限はキュー番号の上限をはるかに弱くします。n個の頂点とm個のエッジを持つグラフのキュー番号は最大で . [ 15 ]この境界はタイトに近い。なぜなら、ランダムなd正則グラフの場合、キューの数は高い確率で、
キュー番号 1 のグラフのブックの厚さは最大で 2 です。[ 17 ] 任意の固定された頂点順序に対して、その順序のブックの厚さとキュー番号の積は、グラフのカット幅をその最大次数で割った値以上になります。 [ 18 ] ブックの厚さはキュー番号よりもはるかに大きくなる場合があります。3 項ハミング グラフは対数的なキュー番号を持ちますが、ブックの厚さは多項式的に大きくなります[ 18 ]また、キュー番号 4 のグラフでブックの厚さが任意に大きくなるものもあります。[ 17 ] Heath、Leighton 、 Rosenberg (1992)は、キュー番号は最大でブックの厚さの線形関数であると推測しましたが、この方向の関数境界は知られていません。3 ページブック埋め込みを持つすべての二部グラフのキュー番号が有界である場合、有界なブックの厚さを持つすべてのグラフのキュー番号も有界であることが知られています。 [ 19 ]
Ganley & Heath (2001) は、グラフのキュー数がその木幅の関数として制限できるかどうかを問い、SV Pemmaraju の未発表の博士論文を引用して、答えはノーである証拠を示した。この証拠から、平面 3-木は無制限のキュー数を持つように見えた。しかし、その後、キュー数は木幅の (二重指数関数) 関数によって制限されることが示された。[ 20 ]平面グラフ、したがって平面 3-木は、その後、キュー数が定数によって制限されることが示された。[ 21 ]
与えられたグラフのキュー番号を決定すること、あるいはこの番号が1であるかどうかをテストすることさえNP完全である。[ 22 ]
しかし、キューレイアウトの頂点順序が入力の一部として与えられる場合、レイアウトの最適なキューの数は、k個のエッジからなるkレインボーの最大エッジ数に等しくなります。k レインボーは、2 つのエッジが入れ子になったペアを形成します。エッジをキューに分割するには、 iレインボー (かつそれより大きいレインボーではない)の外側のエッジeをi番目のキューに割り当てることで実行できます。最適なレイアウトは、 O ( m log(log n ))の時間で構築できます。ここで、n は入力グラフの頂点の数、m はエッジの数を表します。[ 23 ]
キュー数が制限されたグラフは拡張も制限されており、つまり、その浅いマイナーは、エッジと頂点の比率（または同等の縮退度または樹状度）がキュー数とマイナーの深さの関数によって制限される疎グラフです。結果として、サイズが制限されたパターングラフの部分グラフ同型性を含むいくつかのアルゴリズムの問題は、これらのグラフに対して線形時間アルゴリズムを持っています。 [ 24 ]より一般的には、拡張が制限されているため、グラフの1階論理の任意の文が、キュー数が制限された与えられたグラフに対して有効かどうかを線形時間でチェックすることが可能です。[ 25 ]
キューの配置は必ずしも優れた 2 次元グラフ描画を生成するわけではありませんが、3 次元グラフ描画に使用されています。特に、グラフ クラスXのキュー数が有界であるのは、 X内の任意のn頂点グラフGに対して、 Gの頂点をO ( n ) × O (1) × O (1)の 3 次元グリッドに配置して、2 つのエッジ (直線で描画した場合) が互いに交差しないようにできる場合に限ります。[ 26 ]したがって、たとえば、デ ブルイン グラフ、有界木幅のグラフ、平面グラフ、および適切なマイナー閉じたグラフ族は、線形体積の 3 次元埋め込みを持ちます。[ 27 ] [ 28 ] [ 29 ]
