アーク図

弧図は、グラフの頂点をユークリッド平面上の直線上に配置し、その直線の上または下に半円やその他の凸曲線を用いて辺を描くグラフ描画の一種です。これらの図は、線形埋め込み図または回路図とも呼ばれます。

弧図の応用例としては、情報可視化、有理数間の数論的関係を示すファレイ図、RNA二次構造を表す図（図の交点が構造中の擬似結び目を表す）などが挙げられる。

弧図では、グラフの頂点はユークリッド平面上の線に沿って配置されます。辺は、線によって囲まれた 2 つの半平面の 1 つまたは両方に半円として描画されるか、または一連の半円によって形成される滑らかな曲線として描画されます。場合によっては、線自体の線分も辺として使用できますが、その場合は、線に沿って連続する頂点のみを接続している必要があります。半円を他の種類の凸曲線に置き換えたこの描画スタイルのバリエーションも、一般的に弧図と呼ばれます。^{[ 1 ]}

有向グラフの描画では、各弧を時計回りに描くのが一般的な慣例であり、シーケンス内の前の頂点から後の頂点に向かう弧は頂点線の上に描かれ、後の頂点から前の頂点に向かう弧は線の下に描かれる。^{[ 2 ]}

この種の図に「アーク図」という用語が使われるようになったのは、ワッテンバーグ（2002）が 文字列の繰り返しパターンを視覚化するために、同じ部分文字列のペアをアークで結ぶ同様の図を使用したことに由来する。しかし、このグラフ描画のスタイルは、その名前よりもはるかに古く、少なくともサーティ（1964）とニコルソン（1968）の研究にまで遡り、彼らはアーク図を使ってグラフの交差数を研究した。^{[ 3 ]}

アーク図は線形埋め込みとも呼ばれる。^{[ 4 ]} RNA二次構造の回路トポロジーへの応用では、回路図と呼ばれる。^{[ 5 ]}

ニコルソン（1968）が指摘したように、平面上のグラフのあらゆる図は、交点の数を変えることなく、円弧図に変形することができる。特に、すべての平面グラフは平面円弧図を持つ。ただし、この埋め込みでは、一部の辺に複数の半円を使用する必要があるかもしれない。^{[ 6 ]}

グラフが各辺が単一の半円である弧図を使用して交差なしで描画される場合、その図は 2 ページのブック埋め込みになります。この種の図は、平面グラフの真部分集合であるサブハミルトングラフでのみ可能です。 ^{[ 7 ]}例えば、極大平面グラフがこのような埋め込みを持つのは、ハミルトン閉路を含む場合のみです。したがって、ゴールドナー・ハラリーグラフのような非ハミルトン極大平面グラフは、辺ごとに 1 つの半円を持つ平面埋め込みを持つことはできません。^{[ 8 ]}与えられたグラフがこの種の交差のない弧図を持つかどうか (または同等に、ページ番号が 2 であるかどうか) をテストすることはNP 完全です。^{[ 9 ]}

しかし、すべての平面グラフには、各辺が最大で2つの半円を持つ双弧として描かれる弧図が存在します。さらに強く言えば、すべてのst平面有向グラフ（外側面に単一の始点と単一の終点を持つ平面有向非巡回グラフ）には、各辺が単調曲線を形成し、これらの曲線がすべて頂点線の一方の端から他方の端に向かって一貫して方向付けられる弧図が存在します。^{[ 10 ]}無向平面グラフの場合、各辺に最大で2つの半円を持つ弧図を構築する1つの方法は、グラフを細分化して追加の辺を追加し、結果として得られるグラフがハミルトン閉路を持つように（そして各辺が最大で1回細分化されるように）、ハミルトン閉路上の頂点の順序を線に沿った順序として使用することです。^{[ 11 ]}${\displaystyle n}$頂点、最大${\displaystyle n/2}$バイアスアークが必要です。^{[ 12 ]}

与えられたグラフに、辺ごとに半円が 1 つあり、交差がない弧図が存在するかどうかをテストすることは NP 完全であるため、交差の数を最小化するこの種の弧図を見つけることもNP 困難です。この交差最小化問題は、非平面グラフの場合、線に沿った頂点の順序が固定されている場合でも NP 困難のままです。 ^{[ 4 ]}ただし、固定順序の場合、交差のない埋め込み (存在する場合) は、問題を2-充足可能性問題に変換することで多項式時間で見つけることができます。この問題では、変数は各弧の配置を表し、制約は交差する弧が頂点線の同じ側に配置されないようにします。^{[ 13 ]}さらに、固定順序の場合、半円とその潜在的な交差を表す補助グラフで最大カット問題を解くことによって、交差を最小化する埋め込みを近似することができます（または同等に、2充足可能性インスタンスのMAX2SATバージョンを近似することによって）。^{[ 14 ]}

Cimikowski & Shope (1996)、Cimikowski (2002)、およびHe、Sýkora & Vrt'o (2005)は、交差が少ないアーク図を見つけるためのヒューリスティックについて議論しています。

情報可視化のアプリケーションに関して、Heer、Bostock 、 Ogievetsky (2010)は、アーク図は「2 次元レイアウトほどグラフの全体構造を効果的に伝えることはできないかもしれない」が、そのレイアウトによりグラフの頂点に関連付けられた多変量データを簡単に表示できると述べている。^{[ 15 ]}アーク図は、Brandes (1999)によってシフトレジスタの状態図を可視化するために使用され、^{[ 16 ]} Djidjev & Vrt'o (2002)によってすべてのグラフの交差数がそのカット幅と頂点次数の組み合わせによって下限が定められることを示すために使用され、 ^{[ 17 ]} Byrne ら (2007)によってBluetoothデバイス間の相互作用を可視化するために使用され、 ^{[ 18 ]} Owens & Jankun-Kelly (2013)によってアメリカンフットボールの試合のプレーのヤード数を可視化するために使用された。^{[ 19 ]}この可視化手法のその他の応用例については、Nagel & Duval (2013)が概説している。^{[ 1 ]}

有理数の集合を表すファレイ図は、幾何学的に弧図として表現できる構造です。この図では、数直線上に配置された各数に対応する頂点と、数同士を結ぶ線の上に半円形の辺があります。${\displaystyle p/q}$そして${\displaystyle r/s}$（最も簡単に言うと）${\displaystyle |ps-rq|=1}$図の半円は、双曲平面のポアンカレ半平面モデルにおける線と考えることができ、頂点はこのモデルの境界線上の無限点に配置されます。ポアンカレ半平面モデルには、境界線上の点として表されない無限点があり、これはモデル内のすべての垂直光線の共通の終点であり、これは「分数」1/0（数値として定義されていない）で表すことができ、その隣接関係を決定する規則は同じです。任意の有理数の集合のファレイ図は平面グラフであり、すべての有理数の集合のファレイ図は、双曲平面を理想三角形でテセレーションします。^{[ 20 ]}

アーク図または回路図は、タンパク質や核酸（DNA、RNA）などの折り畳まれた生体高分子の研究によく使用されます。生体高分子は通常、図の線に沿ってその主要なモノマー配列で表され、線より上のアークは、配列順序では隣接していなくてもポリマーの物理的構造では隣接しているモノマー（例えば、タンパク質のアミノ酸、RNAまたはDNAの塩基）間の結合を表します。次に、回路トポロジーの理論的枠組みを適用して、局所的および全体的なトポロジー情報を抽出し、折り畳まれた分子の生物学的機能に関連付けることができます。^{[ 21 ]} アークが交差しない場合、2つのアークの配置は、平行（P）または直列（S）のいずれかになります。交差がある場合、その交差は、回路トポロジーでX配置と呼ばれることが多いものを表します。P、S、およびXの統計は、これらのポリマーの折り畳み速度論について学ぶために使用できます。^{[ 22 ]}