本の埋め込み

グラフ理論において、ブック埋め込みは、グラフの平面埋め込みを、境界としてすべて同じ線を持つ半平面の集合であるブックへの埋め込みに一般化したものです。通常、グラフの頂点はこの境界線 (スパインと呼ばれる) 上にある必要があり、辺は単一の半平面内に収まっている必要があります。グラフのブックの厚さは、グラフのブック埋め込みの半平面の最小数です。ブックの厚さは、ページ番号、スタック数、または固定外厚とも呼ばれます。ブック埋め込みは、ページ幅やブック交差数など、 他のいくつかのグラフ不変量を定義するためにも使用されています。

n個の頂点を持つすべてのグラフの本の厚さは最大で であり、この式は完全グラフの正確な本の厚さを与えます。本の厚さが 1 であるグラフは外平面グラフです。本の厚さが最大で 2 であるグラフは部分ハミルトン グラフであり、常に平面です。より一般的には、すべての平面グラフの本の厚さは最大で 4 です。本の背に沿った固定された頂点順序を知っているかどうかに関係なく、与えられたグラフの正確な本の厚さを決定することは NP 困難です。埋め込みの背に沿った頂点の固定された順序が与えられた場合、グラフの 3 ページの本の埋め込みの存在をテストすることは、未知の計算複雑性を持ちます。多項式時間で解けることも、NP 困難であることも知られていません。 ${\displaystyle \lceil n/2\rceil }$

ブック埋め込みを研究する元々の動機の 1 つは、 VLSI設計への応用でした。ブック埋め込みの頂点は回路のコンポーネントを表し、ワイヤはそれらの間の接続を表します。ブック埋め込みはグラフ描画にも応用され、円弧図と円形レイアウトという 2 つの標準的なグラフ視覚化スタイルをブック埋め込みを使用して構築できます。

交通計画では、信号機で出会い相互作用する歩行者と車両の交通のさまざまな出発地と目的地を、さまざまな出発地と目的地のペアを接続するエッジを持つグラフの頂点として数学的にモデル化できます。このグラフのブック埋め込みを使用して、すべての交通が可能な限り少ない信号フェーズで交差点を通過できるようにするスケジュールを設計できます。RNAの折り畳み構造を含むバイオインフォマティクスの問題では、1 ページのブック埋め込みが核酸の二次構造の古典的な形式を表し、2 ページのブック埋め込みが擬似結び目を表します。ブック埋め込みの他の用途には、 抽象代数と結び目理論があります。

位相空間としての本の概念は、1960年代にCAパーシンガーとゲイル・アトネオセンによって定義されました。^{[1] [2]}この研究の一環として、アトネオセンはすでに本へのグラフの埋め込みを検討していました。彼が研究した埋め込みは、他の位相空間へのグラフの埋め込みと同じ定義を使用していました。頂点は個別の点で表され、辺は曲線で表され、2つの辺が交差する唯一の方法は、共通の端点で出会うことです。

1970年代初頭、 ポール・C・カイネンとL・テイラー・オルマンは、その後のほとんどの研究で使用されるようになった、より制限されたタイプの埋め込みを開発しました。彼らの定式化では、グラフの頂点は本の背に沿って配置され、各辺は1ページ内になければなりません。^{[3] [4]}その後の本の埋め込みの発展における重要なマイルストーンには、 1980年代後半のミハリス・ヤナカキスによる、平面グラフの本の厚さは最大で4ページであるという 証明^{[5] [6] 、および1990年代後半の本の埋め込みと}バイオインフォマティクスの密接な関係の発見が含まれます。^[7]

本は特別な種類の位相空間であり、半平面の扇とも呼ばれる。 ^{[1] [8]}本は、本の背または背表紙と呼ばれる単一の直線 ℓと、本のページまたは葉と呼ばれる1つ以上の半平面の集合で構成され、 ^[9]各半平面は背表紙を境界としている。有限のページ数の本は、例えばℓ を直交座標系の z 軸に選び、ページをxz平面に対する二面角が2 π / kの整数倍であるk 個の半平面に選ぶことで、 3次元空間に埋め込むことができる。^[10]

有限グラフ G を本Bに描くことは、 GをBに描くことであり、 Gのすべての頂点はBの背骨上の点として描かれ、Gのすべての辺はBの単一ページ内に含まれる曲線として描かれる。Gのkページ本の交差数は、 kページの本の描画における交差の最小数である。^[11]

GのBへのブック埋め込みは、 GのBへのグラフ埋め込みを形成するブック描画です。つまり、これはエッジ交差のないGのBへのブック描画です。すべての有限グラフには、十分なページ数を持つブックへのブック埋め込みがあります。たとえば、グラフの各エッジを独自の個別のページに埋め込むことは常に可能です。ブックの厚さ、ページ番号、またはGのスタック数は、 Gのブック埋め込みに必要な最小ページ数です 。ページ数以外にブック埋め込みの品質を測定するもう 1 つのパラメーターは、ページ幅です。これは、カット幅と同様に、単一ページ内で背表紙に垂直な光線が交差できるエッジの最大数として定義されます。同様に (各エッジが単調な曲線として描画されるブック埋め込みの場合)、これは、エッジの端点のペアによって背表紙上で定義される間隔がすべて互いに交差するような、単一ページ内のエッジのサブセットの最大サイズです。^{[12] [13] [14]}

これらの定義では、辺が本の1ページ内にとどまることが許可されていることが非常に重要です。アトネオセンがすでに指摘したように、辺が本の背骨を横切って1ページから別のページに移動できる場合、すべてのグラフを3ページの本に埋め込むことができます。^{[15] [2] [16]}背骨の交差が許可されているこのような3ページの位相的な本の埋め込みでは、すべてのグラフを辺ごとに最大で対数の背骨の交差で埋め込むことができ、^[15]一部のグラフではこの数の背骨の交差が必要です。^[17]

最初の図に示されているように、完全グラフ K ₅の本の厚さは3 です。非平面グラフであるため、その本の厚さは 2 より大きくなりますが、3 ページの本の埋め込みが存在します。より一般的には、n ≥ 4 の頂点を持つすべての完全グラフの本の厚さは です。この結果は、任意のn頂点グラフの最大可能な本の厚さの上限も示しています。^[10]${\displaystyle \lceil n/2\rceil }$

完全グラフK _nの2ページ交差数は

${\displaystyle {\frac {1}{4}}{\biggl \lfloor }{\frac {n}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {n-1}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {n-2}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {n-3}{2}}{\biggr \rfloor },}$

このグラフの無制限交差数が何であるべきかというアンソニー・ヒルの未証明の予想に一致する。つまり、ヒルの予想が正しければ、交差数を最小にするこのグラフの描画は2ページの描画になる。^[18]

完全二部グラフ K _{a , b}の本の厚さは最大でもmin( a , b )である。この本の厚さで図を描くには、二部グラフの小さい方の辺の各頂点について、その頂点に接する辺をそれぞれのページに配置すればよい。この制限は常に厳密なわけではない。たとえば、K _4,4の本の厚さは 4 ではなく 3 である。ただし、グラフの両側が非常に不均衡な場合、つまりb > a ( a − 1)の場合、K _{a , b}の本の厚さはちょうどaである。^{[10] [19]}

トゥラングラフ T ( kr , r ) (各独立集合のk頂点からなるr_個の独立集合からなり、異なる独立集合の2頂点の間には辺がある完全な多部グラフ Kk _{, k ,...} )の場合、本の厚さtは

${\displaystyle \left\lceil {\frac {k(r-1)}{2}}\right\rceil \leq t\leq \left\lceil {\frac {kr}{2}}\right\rceil }$

rが奇数の場合には、上限は次のように改善される。

${\displaystyle t\leq (r-1)\left\lceil {\frac {k}{2}}\right\rceil +\left\lceil {\frac {k}{4}}\right\rceil .}$^{[10] [20]}

バイナリ・ド・ブリュイングラフ、シャッフル交換グラフ、およびキューブ連結サイクル（これらのグラフが非平面になるほど大きい場合）の本の厚さは ちょうど3です。 ^[21]

与えられたグラフGの本の厚さは、G が外平面グラフである場合に限り、最大で 1 になります。外平面グラフとは、すべての頂点が埋め込みの外面に属する平面埋め込みを持つグラフです。このようなグラフでは、頂点を外面と同じ順序で背骨に沿って配置すると、与えられたグラフの 1 ページの本の埋め込みが得られます。(グラフの連結点は、外面の周りの頂点の循環順序に必ず複数回現れますが、本の埋め込みにはそれらのコピーの 1 つだけが含まれる必要があります。) 逆に、1 ページの本の埋め込みは自動的に外平面埋め込みになります。グラフが 1 ページに埋め込まれ、別の半平面が背骨に接続されてページが完全な平面に拡張される場合、埋め込みの外面は追加された半平面全体を含み、すべての頂点はこの外面上にあります。^{[10] [12]}

2ページの本の埋め込みはすべて平面埋め込みの特殊なケースである。なぜなら、本の2ページの和集合は平面全体と位相的に同値な空間だからである。したがって、本の厚さが2であるグラフはすべて自動的に平面グラフになる。より正確には、グラフGの本の厚さは、 G がハミルトン閉路を持つ平面グラフのサブグラフである場合に限り、最大で2になる。^[10]グラフに2ページの埋め込みが与えられている場合、（任意のページに）スパインに沿った連続する2つの頂点（まだ隣接していない）間と、スパインの最初の頂点と最後の頂点の間に追加の辺を追加することで、平面ハミルトングラフに拡張できる。ゴールドナー・ハラリ・グラフは、本の厚さが2ではない平面グラフの例である。これは最大平面グラフであるため、平面性を維持しながら辺を追加することはできず、ハミルトン閉路を持たない。^[10]ハミルトンサイクルによるこの特徴から、2ページの本の埋め込みを持つグラフはサブハミルトングラフとも呼ばれます。^[12]

最大次数が高々4であるすべての平面グラフの本の厚さは高々2である。 ^[22] 平面3木の本の厚さは高々3である。^[23]より一般的には、すべての平面グラフの本の厚さは4である。^{[5] [6] [24]} 1986年にミハリス・ヤナカキス^[6]は、本の厚さがちょうど4である平面グラフが存在すると主張した。しかし、その後のジャーナル論文^[5]で発表されたこの主張の詳細な証明は、 2020年にベコスら^[24]が木幅4で、どの本の埋め込みにも4ページを必要とする 平面グラフを提示するまで知られていなかった。

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

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

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

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

本の厚さ2のグラフは平面グラフなので、平面セパレータ定理に従います。つまり、セパレータとは、頂点のサブセットであり、それを除去すると、セパレータ内の頂点のみを含む、最大2 n / 3個の頂点を持つ部分にグラフを分割するものです。ここで、 n はグラフの頂点の数を指します。ただし、本の厚さ3のグラフには、サブ線形サイズのセパレータがないものもあります。^[37]${\displaystyle O({\sqrt {n}})}$

本の埋め込みの 1 ページ内のエッジは、スタック データ構造のように動作する。これは、スタック上のプッシュ操作とポップ操作の任意のシーケンスを考慮し、スタック操作がグラフの頂点に対応し、本の埋め込みの背骨に沿って順番に配置されたグラフを形成することによって形式化できます。次に、スタックからオブジェクトx をポップする各ポップ操作から、 x をプッシュした前のプッシュ操作にエッジを描くと、結果のグラフには自動的に 1 ページの埋め込みが含まれます。このため、グラフのページ番号はスタック番号とも呼ばれています。同様に、キュー データ構造のエンキュー操作とデキュー操作の任意のシーケンスを考慮し、これらの操作を頂点とし、各エンキュー操作と対応するデキューの間にエッジを持つグラフを形成できます。次に、このグラフでは、2 つのエッジはそれぞれ、背骨上の互いに素な間隔を交差するか、カバーします。類推により、研究者はグラフのキュー埋め込みを、各頂点が背骨上にあり、各辺が1ページにあり、同じページ内の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 ページの本の描画の背骨上の固定された頂点の順序の場合、交差数が 0 以外のときに交差数を最小化することも 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) が挙げたブック エンベッディングの研究の主な動機の 1 つは、 VLSI設計におけるフォールト トレラント マルチプロセッサの構成への応用です。これらの著者が開発した DIOGENES システムでは、マルチプロセッサ システムのCPU は、本の背表紙に対応する論理シーケンスに配置されます (ただし、このシーケンスは、このシステムの物理レイアウトで必ずしも 1 本の線に沿って配置されるわけではありません)。これらのプロセッサを接続する通信リンクは、本のページに対応する「バンドル」にグループ化され、スタックのように動作します。つまり、プロセッサの 1 つを新しい通信リンクの開始に接続すると、バンドル内の以前のリンクがすべて上に押し出され、別のプロセッサを通信リンクの終了に接続すると、バンドルの一番下にあるプロセッサに接続され、他のすべてのリンクが下に押し出されます。このスタックの動作により、1 つのバンドルで、ブック エンベッディングの 1 ページの端を形成する一連の通信リンクを処理できます。このようにリンクを整理することで、どのプロセッサが故障したかに関係なく、ネットワークを実装するのに十分な数の故障していないプロセッサが残っている限り、多種多様なネットワークトポロジを実装できます。このシステムで実装できるネットワークトポロジは、利用可能なバンドルの数に等しい最大の厚さの本を持つものです。^[41] ブックエンベディングは、VLSIコンポーネントを回路の層に接続するワイヤの配置をモデル化するためにも使用できます。^[51]

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

Kainen (1990) が説明したように、ブック エンベッディングは、制御された交差点での交通信号の位相を説明するために使用できます。交差点では、交通の流入車線と流出車線 (歩行者横断歩道と自転車レーンの端、および自動車レーンを含む) は、交差点の周りを時計回りの順序でブック エンベッディングの背骨上に配置されたグラフの頂点として表すことができます。交通が流入車線から流出車線に到達するために交差点を通過するパスは、無向グラフのエッジとして表すことができます。たとえば、このグラフには、同じ道路セグメントに属する流入車線から流出車線へのエッジがあり、ジャンクションで U ターンが許可されている場合に限り、そのセグメントからそのセグメントに戻る U ターンを表します。これらのエッジの特定のサブセットについて、サブセットが、2 つのエッジが本の埋め込みの 1 ページに配置された場合に交差するエッジのペアを含まない場合に限り、互いに干渉することなく通過できるパスのコレクションを表します。したがって、このグラフの本の埋め込みは、パスを干渉しないサブセットに分割することを表し、このグラフの本の厚さ (背骨に固定された埋め込みを含む) は、ジャンクションを通過するすべての可能なトラフィック パスを含む信号スケジュールに必要な最小の異なるフェーズ数を示します。^[53]

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

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

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

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

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

2ページ以上のブック埋め込みは、グラフの3次元描画を構築するためにも使用されています。特に、Wood (2002) は、各ページ内の各頂点の次数を低く保つブック埋め込みの構成を使用して、グラフを低ボリュームの3次元グリッドに埋め込む方法の一部として使用しました。^[57]

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

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

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

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

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

マッケンジーとオーバーベイ（2010）は、有限局所環の零因子から定義されるグラフを用いて、零因子ごとに頂点を作り、積がゼロとなる値のペアごとに辺を作ることで、抽象代数における本の厚さの応用を研究した。^[70]

ディンニコフは複数の論文シリーズで、結び目とリンクの位相的な埋め込みを研究し、これらの埋め込みはシンボルの組み合わせシーケンスで記述できること、2つのリンクの位相的な等価性は埋め込みに対する一連のローカルな変更によって実証できることを示した。^{[71] [72]}