書籍の埋め込み

与えられたグラフGの本の厚さが最大で 1 であるのは、G が外平面グラフである場合に限る。外平面グラフとは、すべての頂点が埋め込みの外側の面に属する平面埋め込みを持つグラフのことである。このようなグラフの場合、外面と同じ順序で頂点を背表紙に沿って配置すると、与えられたグラフの 1 ページの本埋め込みが得られる。（グラフの関節点は、外面の周りの頂点の巡回順序に必ず複数回現れるが、それらのコピーのうち 1 つだけが本埋め込みに含まれるべきである。）逆に、1 ページの本埋め込みは自動的に外平面埋め込みとなる。なぜなら、グラフが 1 ページに埋め込まれ、そのページを完全な平面に拡張するために別の半平面が背表紙に取り付けられると、埋め込みの外面には追加された半平面全体が含まれ、すべての頂点がこの外面上に位置するからである。^{[ 10 ] [ 12 ]}

2 ページ分の書籍埋め込みはすべて平面埋め込みの特殊なケースです。なぜなら、書籍の 2 ページの和集合は、位相的に平面全体と等価な空間だからです。したがって、書籍の厚さが 2 のグラフはすべて自動的に平面グラフになります。より正確には、グラフGの書籍の厚さが最大で 2 になるのは、G がハミルトン閉路を持つ平面グラフの部分グラフである場合のみです。^{[ 10 ]}グラフに 2 ページ埋め込みが与えられた場合、既に隣接していない背骨に沿った任意の 2 つの連続する頂点間、および最初と最後の背骨の頂点間に (任意のページに) 追加のエッジを追加することにより、平面ハミルトングラフに拡張できます。ゴールドナー・ハラリー グラフは、書籍の厚さが 2 ではない平面グラフの例です。これは極大平面グラフであるため、平面性を維持しながらエッジを追加することはできず、ハミルトン閉路もありません。^{[ 10 ]}ハミルトン閉路によるこの特徴付けにより、2ページ分の書籍埋め込みを持つグラフは、サブハミルトングラフとしても知られています。^{[ 12 ]}

最大次数が最大で 4 であるすべての平面グラフは、最大で 2 のブック厚さを持ちます。 ^{[ 22 ]}平面 3-ツリーは、^最大で 3 のブック厚さを持ちます。^{[ 23 ]}より一般的には、すべての平面グラフは 4 のブック厚さを持ちます。^{[ 5 ] [ 6 ] [ 24 ]} 1986 年にMihalis Yannakakisは^、ブック厚さがちょうど 4 である平面グラフが存在すると主張しました。 ^{[ 6 ] しかし、この主張の詳細な証明は、その後のジャーナル論文で発表されましたが、 [ 5 ]} 2020 年に Bekos らが、任意のブック埋め込みで 4 ページを必要とする木幅4 の平面グラフを発表するまで知られていませんでした。 ^{[ 24 ]}

グラフの各辺を2辺パスに分割し、各辺内に新しい頂点を追加すると、ブックの厚さが増加する場合があります。たとえば、ダイヤモンドグラフのブックの厚さは1（外平面グラフ）ですが、その分割グラフのブックの厚さは2（平面グラフであり、サブハミルトングラフですが、外平面グラフではありません）になります。しかし、この分割プロセスによって、分割されたグラフのブックの厚さが大幅に減少する場合もあります。たとえば、完全グラフK _nのブックの厚さは頂点の数に比例しますが、各辺を2辺パスに分割すると、ブックの厚さがはるかに小さい分割グラフが生成されます。${\displaystyle O({\sqrt {n}})}$[ ^{25 ]}このような例が存在するにもかかわらず、Blankenship & Oporowski (1999)は^、分割されたグラフのブックの厚さは元のグラフのブックの厚さよりも小さくなりすぎることはないだろうと推測した。具体的には、任意のグラフGと、 Gのすべてのエッジを2 エッジのパスに置き換えて形成されたグラフHに対して、 Hのブックの厚さがtであれば、 Gのブックの厚さは最大でf ( t )となるような関数f が存在すると推測した。^{[ 16 ]}彼らの推測は誤りであることが判明した。星型グラフと三角形タイリングのデカルト積によって形成されるグラフのブックの厚さは無限大であるが、エッジを 6 エッジのパスに分割すると、ブックの厚さは 3 に減少する。^{[ 26 ]}

本の厚さは、与えられたグラフのエッジを覆うために必要な平面グラフの数である厚さと関連しています。グラフG は、平面上に描画でき、エッジがθ色で着色され、同じ色のエッジ同士が交差しない場合に、厚さ θ を持ちます。同様に、グラフGは、半平面上に描画でき、頂点が半平面の境界上にあり、エッジが θ 色で着色され、同じ色の 2 つのエッジが交差しない場合に、本の厚さ θを持ちます。この本の厚さの定式化では、エッジの色は本の埋め込みのページに対応します。ただし、厚さと本の厚さは互いに大きく異なる場合があります。厚さが 2 であるにもかかわらず、^無制限の本の厚さを持つグラフ (完全グラフの細分化)^が存在します。^{[ 25 ] [ 15 ] [ 16 ]}

木幅kのグラフのブック厚は最大でk + 1であり^{[ 27 ] [ 28 ]}、この上限は k > 2の場合にタイトである。^{[ 27 ]} mエッジのグラフのブック厚は${\displaystyle O({\sqrt {m}})}$^{[ 29 ]}また、種数gのグラフは本の厚さを持つ${\displaystyle O({\sqrt {g}})}$^{[ 30 ]}より一般的には、マイナーで閉じたグラフ族はすべてブックの厚さが制限されていると述べられています。 ^{[ 31 ] [ 32 ]}しかし、この主張の証明は、向き付け不可能な曲面に埋め込まれたグラフはブックの厚さが制限されているという以前の主張に基づいています。この主張の詳細な証明は提供されていません。[ ^{33 ]マイナー}で閉じていない1 平面グラフは、ブックの厚さが制限されていますが、^{[ 31 ]} K _2,2,2,2を含むいくつかの 1 平面グラフは、^{少なくとも4}のブックの厚さを持っています^{。[ 35 ]}

ブックの厚さが制限されているグラフの浅いマイナーはすべて疎グラフであり、そのエッジと頂点の比率は、マイナーの深さとブックの厚さのみに依存する定数によって制限されます。つまり、Nešetřil & Ossona de Mendez (2012)の用語では、ブックの厚さが制限されているグラフは拡張が制限されています。^{[ 31 ]}しかし、拡張が制限されているよりもはるかに強い要件である次数が制限されているグラフでさえ、ブックの厚さが制限されない場合があります。^{[ 36 ]}

本の厚さが２のグラフは平面グラフであるため、平面分離定理に従います。つまり、分離点、つまり頂点のサブセットが存在し、それを取り除くとグラフはそれぞれ最大で２n /3個の頂点を持つ断片に分割され、${\displaystyle O({\sqrt {n}})}$セパレータ内の頂点。ここで、n はグラフ内の頂点の数を表します。ただし、サブリニアサイズのセパレータを持たないブック厚さ 3 のグラフも存在します。^{[ 37 ]}

書籍埋め込みの単一ページ内のエッジは、ある意味でスタックデータ構造のように振る舞います。これは、スタックに対する任意のプッシュ操作とポップ操作のシーケンスを考え、スタック操作がグラフの頂点に対応し、書籍埋め込みの背表紙に沿って順序どおりに配置されたグラフを形成することで形式化できます。次に、スタックからオブジェクトxをポップする各ポップ操作から、 xをプッシュした前のプッシュ操作にエッジを引くと、結果として得られるグラフは自動的に 1 ページの埋め込みになります。このため、グラフのページ番号はスタック番号とも呼ばれています。同様に、キューデータ構造の任意のエンキュー操作とデキュー操作のシーケンスを考え、これらの操作を頂点とし、単一ページの背表紙に順序どおりに配置され、各エンキュー操作と対応するデキュー操作の間にエッジを持つグラフを形成することもできます。すると、このグラフでは、2 つのエッジは背表紙上の互いに素な区間を交差するか、またはカバーします。類推により、研究者たちはグラフのキュー埋め込みを、各頂点が背表紙上にあり、各辺が単一のページにあり、同じページ内の任意の 2 つの辺が背表紙上の互いに素な区間を交差するか覆うような、トポロジーの本への埋め込みとして定義した。グラフのキュー埋め込みに必要な最小ページ数をキュー番号と呼ぶ。^{[ 31 ] [ 38 ] [ 39 ]}

グラフのブックの厚さを求めることはNP困難である。これは、極大平面グラフにおけるハミルトン閉路の発見がNP完全であるという事実から導かれる。^{[ 40 ]}極大平面グラフでは、ハミルトン閉路が存在する場合に限り、ブックの厚さは2となる。したがって、与えられた極大平面グラフのブックの厚さが2であるかどうかをテストすることもNP完全である。^{[ 41 ]}

埋め込みのスパインに沿ったグラフの頂点の順序が固定されている場合、与えられたグラフにスパイン順序で頂点を結ぶサイクルを追加して形成されるグラフの平面性テストのインスタンスとして、2 ページ埋め込み (存在する場合) を線形時間で見つけることができます。[ 7 ^{] Unger (} 1992)は、固定されたスパイン順序を持つ 3 ページ埋め込みを見つけることも多項式時間で実行できると主張しましたが、この結果の記述では多くの詳細が省略されています。^{[ 42 ]}しかし、4 ページ以上を必要とするグラフの場合、円の弦の交差グラフである円グラフの彩色という NP 困難問題との等価性により、可能な限り最小のページ数を持つ 埋め込みを見つける問題は NP 困難のままです。頂点の背表紙の順序が固定されたグラフGが与えられた場合、これらの頂点を円周上に同じ順序で描画し、Gの辺を線分として描画すると、 Gを表す弦の集合が生成されます。次に、この図の弦を頂点とし、交差する弦のペアを辺とする円グラフを形成できます。円グラフの彩色は、Gの辺を、1 ページに交差せずに描画できる部分集合に分割することを表します。したがって、最適な彩色は最適な本の埋め込みと同等です。4 色以上の円グラフ彩色は NP 困難であり、任意の円グラフは何らかの本の埋め込み問題からこのように形成できるため、最適な本の埋め込みも NP 困難であることがわかります。^{[ 43 ] [ 44 ] [ 45 ]} 2 ページの本の描画の背表紙上の頂点の順序が固定されている場合、交差数がゼロでない場合、交差数を最小化することも NP 困難です。^{[ 44 ]}

スパイン順序が不明だが、エッジを 2 ページに分割することが与えられている場合、SPQR ツリーに基づくアルゴリズムによって、 2 ページ埋め込み (存在する場合) を線形時間で見つけることが可能です。^{[ 46 ] [ 47 ]}ただし、スパイン順序もエッジ分割も不明な場合、2 ページ埋め込みを見つけることは NP 完全です。グラフのブッククロッシング数を見つけることも NP 困難です。これは、2 ページクロッシング数がゼロかどうかをテストする特殊なケースが NP 完全であるためです。

拡張が限定されている結果として、より大きなグラフのブックの厚さが限定されている場合、サイズが限定されたパターン グラフがより大きなグラフのサブグラフとして存在するかどうかを調べるサブグラフ同型問題は線形時間で解くことができます。パターン グラフがより大きなグラフの誘導サブグラフであるかどうか、またはより大きなグラフとのグラフ準同型性を持つかどうかを検出する場合も同様です。 ^{[ 48 ] [ 49 ]}同じ理由で、ブックの厚さが限定されたグラフが与えられた一階述語論理の式に従うかどうかをテストする問題は、固定パラメータで扱いやすいです。^{[ 50 ]}

Bekos、Kaufmann 、 Zielke（2015）は、問題をブール充足可能性問題のインスタンスに変換し、結果として得られる問題にSATソルバーを適用することで、最適な書籍埋め込みを見つけるシステムについて説明しています。彼らは、このシステムが400頂点の最大平面グラフの最適な埋め込みを約20分で見つけることができると述べています。^{[ 35 ]}

Chung、Leighton 、 Rosenberg (1987)が挙げたブックエンベディング研究の主な動機の一つは、 VLSI設計におけるフォールトトレラントマルチプロセッサの構成への応用である。これらの著者らが開発した DIOGENES システムでは、マルチプロセッサ システムのCPU は、本の背表紙に対応する論理的な順序で配置される (ただし、この順序は必ずしもシステムの物理的なレイアウトで一直線上に配置されるとは限らない)。これらのプロセッサを接続する通信リンクは、本のページに対応する「バンドル」にグループ化され、スタックのように機能する。あるプロセッサを新しい通信リンクの先頭に接続すると、バンドル内の以前のすべてのリンクが上に押し上げられ、別のプロセッサを通信リンクの末尾に接続すると、バンドルの一番下のリンクに接続され、他のすべてのリンクが下に押し下げられる。このスタック動作により、単一のバンドルで、ブックエンベディングの 1 ページの端を形成する一連の通信リンクを処理できる。このようにリンクを整理することで、ネットワークを実装するのに十分な数の正常なプロセッサが残っている限り、どのプロセッサが故障したかに関係なく、さまざまなネットワークトポロジを実装できます。このシステムで実装できるネットワークトポロジは、利用可能なバンドルの数に等しいブックの厚さを持つものと正確に一致します。^{[ 41 ]} ブック埋め込みは、VLSIコンポーネントを回路の層に接続するワイヤの配置をモデル化するためにも使用できます。^{[ 51 ]}

Chung、Leighton 、 Rosenberg (1987)が挙げた別の応用例は、スタックを使用した順列のソートに関するものです。Donald Knuth ( 1968 )の影響力のある結果では、入力要素をスタックにプッシュし、適切なタイミングでスタックから出力ストリームにポップすることでデータストリームを処理するシステムは、初期順序が順列パターン231を回避する順列で記述されている場合に限り、データをソートできることが示されました。 ^{[ 52 ]}それ以来、スタックとキューのより一般的なシステムによるデータストリームのソートという同様の問題について多くの研究が行われてきました。Chung 、Leighton 、 Rosenberg (1987)が検討したシステムでは、入力データストリームの各要素は、複数のスタックのいずれかにプッシュする必要があります。そして、このようにしてすべてのデータがプッシュされたら、これらのスタックから (適切な順序で) アイテムが出力ストリームにポップされます。Chung らは、観察すると、与えられた順列は、その順列から派生した特定のグラフが、背表紙に沿ってある一定の順序で頂点を持ち、ページ数がスタックの数以下であるブック埋め込みを持つ場合に限り、このシステムによってソートできる。^{[ 41 ]} 

カイネン（1990）が説明したように、ブック埋め込みは、制御された交差点における交通信号のフェーズを記述するために使用できます。交差点では、交通の流入車線と流出車線（歩行者横断歩道や自転車レーンの終端、自動車レーンを含む）は、グラフの頂点として表現され、交差点の周囲を時計回りの順序でブック埋め込みの背表紙に配置されます。交通が流入車線から流出車線に移動するために交差点を通過する経路は、無向グラフのエッジとして表現できます。たとえば、このグラフには、同じ道路セグメントに属する流入車線から流出車線へのエッジがあり、交差点でUターンが許可されている場合に限り、そのセグメントからそのセグメントに戻るUターンを表します。これらのエッジの特定の部分集合について、その部分集合は、2 つのエッジをブック埋め込みの 1 つのページに配置した場合、交差するエッジのペアをその部分集合に含まない場合のみ、互いに干渉することなく通過できるパスの集合を表します。したがって、このグラフのブック埋め込みは、パスを干渉しない部分集合に分割したものを表し、このグラフのブックの厚さ (背表紙に固定された埋め込み) は、交差点を通過するすべての可能な交通経路を含む信号スケジュールに必要な最小の異なるフェーズ数を与えます。^{[ 53 ]}

ブック埋め込みは、ネットワークデータの可視化にも頻繁に適用されています。グラフ描画の標準的なレイアウトであるアーク図^{[ 54 ]}と円形レイアウト^{[ 55 ]は、ブック埋め込みと見なすことができ、ブック埋め込みはクラスタレイアウト[ 46 ]} 、同時埋め込み^{[ 56 ]} 、および3次元グラフ描画^{[ 57 ]}の構築にも適用されています。

アーク図^{[ 54 ]}または線形埋め込み^{[ 44 ]}は、グラフの頂点を線上に配置し、グラフのエッジをこの線の上または下の半円として描画します。場合によっては、エッジを線分上に描画することもできます。この描画スタイルは、1 ページ (すべての半円が線の上にある場合) または 2 ページ (線の両側を使用する場合) のブック埋め込みに対応し、元々はグラフの交差数を研究する方法として導入されました。 [ ^{58 ] [ 59 ] 2}ページのブック埋め込みを持たない平面グラフも、エッジを線の上下に複数の半円で表現することで同様の方法で描画できます。このような描画は通常の定義によるブック埋め込みではありませんが、トポロジカルブック埋め込みと呼ばれています。 [ ^{60 ]すべて}の平面グラフに対して、各エッジが背表紙を最大 1 回だけ横切るような埋め込みを常に見つけることができます。^{[ 61 ]}

別の描画スタイルである円形レイアウトでは、グラフの頂点が円上に配置され、辺は円の内側または外側に描かれます。^{[ 55 ]}また、辺を円の内側に配置する（例えば直線セグメントとして）と、1ページの本の図に対応し、円の内側と外側の両方に配置すると、2ページの本の図に対応します。^{[ 62 ]}

どちらのスタイルの 1 ページ図面でも、図面の視覚的な煩雑さを軽減する方法として、交差の数を少なく保つことが重要です。交差の数を最小化することはNP 完全ですが、^{[ 44 ]}頂点の数をnとすると、 O (log ² n ) の近似比で近似できます。 ^{[ 63 ]} 1 ページまたは 2 ページの交差数を最小化することは、与えられたグラフのサイクロマチック数、または交差数とグラフの木幅の組み合わせによってパラメータ化されている場合、固定パラメータで扱い可能です。 ^{[ 64 ] [ 65 ]}交差の複雑さを軽減するためのヒューリスティックな方法も考案されており、たとえば、慎重な頂点挿入順序と局所最適化に基づいています。^{[ 55 ]}

エッジをページに固定した2ページブック埋め込みは、クラスタリングされた平面性の一形態として解釈できます。この場合、与えられたグラフは、グラフの一部（エッジの2つのサブセット）がクラスタリングを反映するように描画される必要があります。^{[ 46 ]} 2ページブック埋め込みは、グラフの同時埋め込みを見つけるためにも使用されています。同時埋め込みでは、同じ頂点セット上に2つのグラフが与えられ、両方のグラフが直線エッジで平面的に描画されるような頂点の配置を見つける必要があります。^{[ 56 ]}

2ページを超える書籍埋め込みも、グラフの3次元図を作成するために使用されてきました。特に、Wood (2002)は、各ページ内の各頂点の次数を低く保つ書籍埋め込みの構成を、低体積の3次元グリッドにグラフを埋め込む方法の一部として使用しました。^{[ 57 ]}

RNA分子がどのように折り畳まれて構造を形成するかを研究する際、核酸二次構造の標準的な形式は、線に沿って描かれた塩基の鎖（RNA配列自体）と、その線より上にある構造の塩基対を表す弧の集合として図式的に記述できます。つまり、これらの構造は実際には複雑な三次元形状を持っていますが、その接続性（二次構造が存在する場合）は、より抽象的な構造、つまり1ページの本の埋め込みによって記述できます。しかし、すべてのRNAの折り畳みがこのように単純に振る舞うわけではありません。HaslingerとStadler（1999）は、特定のRNA擬似結び目に対して、2ページの本の埋め込みの形をとるいわゆる「二重二次構造」を提案しました。RNA配列は再び線に沿って描かれますが、塩基対はこの線の上と下の両方に弧として描かれます。二重二次構造を形成するには、グラフの最大次数が3以下である必要があります。各塩基は、塩基配列内の隣接する塩基への2つのリンクに加えて、図の1つの弧にのみ参加できます。この定式化の利点としては、実際に空間的に結び目になっている構造を除外できること、そして既知のほとんどのRNA擬似結び目に一致することが挙げられる。^{[ 7 ]}

このアプリケーションでは、脊椎の順序が事前にわかっているため、与えられた塩基対に対して二部構造が存在するかどうかをテストするのは簡単です。 2 つのページに互換性のある方法でエッジを割り当てる問題は、2-充足可能性のインスタンスとして、または頂点が塩基対であり、エッジが塩基対間の交差を表す円グラフの二部グラフ性をテストする問題として定式化できます。 ^{[ 7 ]}あるいは、 HaslingerとStadler (1999)が示すように、より効率的に 、入力のダイアグラムグラフ(塩基をその配列順にサイクルに接続し、与えられた塩基対をエッジとして追加することによって形成されるグラフ) が平面グラフである場合に限り、二部構造が存在します。^{[ 7 ]}この特徴付けにより、二部構造は平面性テストのインスタンスとして線形時間で認識できます。

Blin ら (2007) は、 RNA 二次構造比較における特定の問題のNP 困難性の証明の一部として、二次構造と書籍埋め込みの関係を利用しました。 ^{[ 66 ]}また、RNA 構造が 2 つの二次構造ではなく三次構造である場合 (つまり、図に 2 ページ以上必要な場合)、ページ番号の決定は再び NP 困難になります。^{[ 67 ]}

Pavan、Tewari 、 Vinodchandran (2012)は、有向グラフにおける到達可能性問題の計算複雑性理論を研究するためにブック埋め込みを使用しました。彼らが指摘したように、2 ページ有向グラフの到達可能性は、非曖昧対数空間 (対数空間複雑性における非曖昧多項式時間問題のクラスUPの類似物) で解決できます。しかし、3 ページ有向グラフの到達可能性には、非決定性対数空間の完全な能力が必要です。したがって、ブック埋め込みは、これら 2 つの複雑性クラスの区別と密接に関連しているようです。^{[ 68 ]}

定数ページ番号を持つエキスパンダーグラフの存在^{[ 37 ]}は、1テープ非決定性チューリングマシンによる2テープ非決定性チューリングマシンの準2次時間シミュレーションが存在しないことを証明する重要なステップである^{[ 69 ] 。}

McKenzie & Overbay (2010) は、有限局所環の零因子から定義されたグラフを使用して、各零因子に頂点を、積がゼロとなる値のペアごとに辺を作成することで、抽象代数における本の厚さの応用を研究している。^{[ 70 ]}

複数の論文シリーズにおいて、Dynnikovは結び目とリンクの位相的ブック埋め込みを研究し、これらの埋め込みは記号の組み合わせ列で記述できること、および2つのリンクの位相的等価性は埋め込みへの局所的な変更のシーケンスによって実証できることを示した。^{[ 71 ] [ 72 ]}