アーク図

ゴールドナー・ハラリーグラフの円弧図。このグラフはハミルトングラフではありませんが、赤い破線セグメントが交差するエッジを細分化し、このセグメントに沿って 2 つのエッジを追加することでハミルトングラフにすることができます。

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

この種の描画に「アーク図」という語句が使われるようになったのは、Wattenberg (2002) が、等しい部分文字列のペアをアークで接続することで、文字列の繰り返しパターンを視覚化するために同様のタイプの図を使用したことに倣ったものである。しかし、このスタイルのグラフ描画は、その名前よりはるかに古く、Saaty (1964) と Nicholson (1968) の研究にまで遡る。彼らはアーク図を使用してグラフの交差数を研究した。アーク図の古い名前だがあまり使用されていない名前は、線形埋め込みである。^{[2]最近では、アーク図は結び目や絡まりの}回路トポロジーのフレームワーク内で使用されており、回路図と呼ばれている。^[3]

Heer、Bostock、Ogievetsky (2010) は、円弧図は「2 次元レイアウトほどグラフの全体構造を効果的に伝えることはできないかもしれない」が、そのレイアウトにより、グラフの頂点に関連付けられた多変量データを簡単に表示できると書いています。円弧図の応用には、有理数間の数論的接続を視覚化したFarey 図や、図の交差が構造内の擬似結び目を表す RNA 二次構造を表す図などがあります。

平面グラフ

ニコルソン (1968) が観察したように、平面上のグラフの描画はすべて、交差数を変えずに円弧図に変形できます。特に、すべての平面グラフには平面円弧図があります。ただし、この埋め込みでは、一部の辺に複数の半円を使用する必要がある場合があります。

各辺が単一の半円である円弧図を使用してグラフが交差なしで描画された場合、その描画は2ページの本の埋め込みであり、平面グラフの適切な部分集合であるサブハミルトングラフでのみ可能です。 ^[4]たとえば、最大平面グラフがそのような埋め込みを持つのは、ハミルトン閉路が含まれている場合のみです。したがって、ゴールドナー-ハラリーグラフなどの非ハミルトン最大平面グラフは、辺ごとに1つの半円を持つ平面埋め込みを持つことはできません。与えられたグラフにこのタイプの交差のない円弧図があるかどうか（または同等に、ページ番号が2であるかどうか）をテストすることはNP完全です。^[5]

しかし、すべての平面グラフには、各辺が最大で 2 つの半円を持つ二円弧として描かれる円弧図があります。さらに強い意味としては、すべてのst平面有向グラフ (単一のソースと単一のシンクが両方とも外側にある平面有向非巡回グラフ) には、すべての辺が単調な曲線を形成し、これらの曲線がすべて頂点ラインの一方の端からもう一方の端に向かって一貫して向いている円弧図があります。 ^[6]無向平面グラフの場合、1 辺あたり最大で 2 つの半円を持つ円弧図を作成する 1 つの方法は、グラフを細分化して余分な辺を追加し、結果のグラフにハミルトン閉路が含まれるようにし(各辺が最大で 1 回細分化されるようにし)、ハミルトン閉路上の頂点の順序をラインに沿った順序として使用することです。^[7]頂点を持つ平面グラフでは、最大で二円弧が必要です。^[8] $n$ $n/2$

交差を最小限に抑える

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

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

時計回り

有向グラフを描く場合、一般的な慣習として各弧を時計回りに描くことがあり、これにより、シーケンス内の前の頂点から後の頂点に向かう弧は頂点の線の上に描かれ、後の頂点から前の頂点に向かう弧は線の下に描かれます。この時計回りの方向の慣習は、Fekete ら (2003) によって異なるグラフ描画スタイルの一部として開発され、Pretorius と van Wijk (2007) によって弧図に適用されました。

アプリケーション

有理数集合のファレー図は、弧図として幾何学的に表現できる構造である。この形式では、数直線上に配置された各数の頂点と、数と(最も簡単に言えば)のペアを結ぶ線の上に半円の辺がある。図の半円は、双曲面のポアンカレ半平面モデルの線と考えることができ、頂点はこのモデルの境界線上の無限の点に配置される。ポアンカレ半平面モデルには、境界線上の点として表されない無限の点があり、これはモデル内のすべての垂直線の共有端点であり、これは「分数」1/0 (数として定義されていない) で表すことができ、隣接関係を決定するための同じ規則がある。任意の有理数集合のファレー図は平面グラフであり、すべての有理数集合のファレー図は、理想的な三角形による双曲面のモザイク模様を形成する。^[11] $p/q$ $r/s$ $|ps-rq|=1$

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

アーク図は、Brandes (1999) がシフトレジスタの状態図を視覚化するために使用し、Djidjev & Vrt'o (2002) がすべてのグラフの交差数がそのカット幅と頂点の次数の組み合わせによって下限が定められていることを示すために使用し、Byrne ら (2007) がBluetoothデバイス間の相互作用を視覚化するために使用し、Owens & Jankun-Kelly (2013) がアメリカンフットボールの試合でのプレーのヤード数を視覚化するために使用しました。この視覚化手法のその他の応用については、Nagel & Duval (2013) が調査しています。

注記

^ ナゲル＆デュバル（2013年）。
^ ab 増田ら（1990）。
^ Alireza MashaghiとRoland van der Veen、分子回路トポロジー対称性の多項式不変量13(9)、1751（2021）
^ 本の埋め込みにおけるエッジレイアウトへの半円の応用は、Bernhart & Kainen (1979) によってすでに行われていましたが、円弧図と 2 ページの本の埋め込みとの明確な関連は、Masuda et al. (1990) によるものと思われます。
^ チャン、レイトン、ローゼンバーグ（1987年）。
^ ジョルダーノら（2007年）。
^ Bekos et al. (2013).
^ Cardinal et al. (2018).
^ エフラット、エルテン、コボロフ（2007年）。
^ Cimikowski & Mumey (2007).
^ ギルマン＆キーン（2002年）。
^ マシャギ、アリレザ;ファン・ワイク、ローランド・J.タンズ、サンダー J. (2014)。「タンパク質と核酸の回路トポロジー」。構造。22 (9): 1227–1237。土井：10.1016/j.str.2014.06.015。PMID 25126961。
^ Mugler, Andrew; Tans, Sander J.; Mashaghi, Alireza (2014). 「自己相互作用鎖の回路トポロジー：フォールディングおよびアンフォールディングダイナミクスへの影響」. Phys. Chem. Chem. Phys . 16 (41): 22537–22544. Bibcode :2014PCCP...1622537M. doi :10.1039/C4CP03402C. PMID 25228051.

参考文献

Bekos, Michael A.; Kaufmann, Michael; Kobourov, Stephen G.; Symvonis, Antonios (2013)、「滑らかな直交レイアウト」、グラフ描画: 第 20 回国際シンポジウム、GD 2012、レドモンド、ワシントン州、米国、2012 年 9 月 19 ～ 21 日、改訂選択論文、Lecture Notes in Computer Science、vol. 7704、Springer、pp. 150 ～ 161、doi : 10.1007/978-3-642-36763-2_14、ISBN 978-3-642-36762-5。
バーンハート、フランク R.;カイネン、ポール C. (1979)、「グラフの本の厚さ」、組み合わせ理論ジャーナル、シリーズ B、27 (3): 320–331、doi : 10.1016/0095-8956(79)90021-2。
Brandes, Ulrik (1999)、「Hunting down Graph B」、Graph Drawing: 7th International Symposium、GD'99、Štiřín Castle、チェコ共和国、1999 年 9 月 15 ～ 19 日、議事録、Lecture Notes in Computer Science、vol. 1731、Springer、pp. 410 ～ 415、doi : 10.1007/3-540-46648-7_42、ISBN 978-3-540-66904-3。
Byrne, Daragh、Lavelle, Barry、Jones, Gareth JF、Smeaton, Alan F. (2007)、「Bluetooth の相互作用を視覚化する: Arc ダイアグラムと DocuBurst テクニックを組み合わせる」(PDF)、Ormerod, Thomas C.、Sas, Corina (編)、第 21 回 British HCI グループ年次会議 HCI 2007 の議事録: HCI...ただし、私たちが知っているようなものではありません - 第 2 巻、BCS HCI 2007、ランカスター大学、英国、2007 年 9 月 3 ～ 7 日、英国コンピュータ協会、pp. 129 ～ 132。
Cardinal, Jean; Hoffmann, Michael; Kusters, Vincent; Tóth, Csaba D.; Wettstein, Manuel (2018)、「円弧図、反転距離、およびハミルトン三角形分割」、計算幾何学、68 : 206–225、arXiv : 1611.02541、doi :10.1016/j.comgeo.2017.06.001、MR 3715053、S2CID 1169465
チャン、ファン RK ;レイトン、フランクトンプソン;ローゼンバーグ、アーノルド L. (1987)、「書籍へのグラフの埋め込み: VLSI 設計への応用に関するレイアウト問題」(PDF)、SIAM Journal on Algebraic and Discrete Methods、8 (1): 33–58、doi :10.1137/0608002。
Cimikowski, Robert (2002)、「固定線形交差数問題に対するアルゴリズム」、離散応用数学、122 (1–3): 93–115、doi : 10.1016/S0166-218X(01)00314-6、MR 1907825。
Cimikowski, Robert; Mumey, Brendan (2007)、「固定線形交差数の近似」、離散応用数学、155 (17): 2202–2210、doi : 10.1016/j.dam.2007.05.009、MR 2360650。
Cimikowski, Robert; Shope, Paul (1996)、「グラフレイアウト問題に対するニューラルネットワークアルゴリズム」、IEEE Transactions on Neural Networks、7 (2): 341–345、doi :10.1109/72.485670、PMID 18255588。
Djidjev, Hristo; Vrt'o, Imrich (2002)、「交差数の改良された下限値」、Graph Drawing: 9th International Symposium、GD 2001、オーストリア、ウィーン、2001 年 9 月 23 ～ 26 日、改訂版論文、Lecture Notes in Computer Science、vol. 2265、Springer、pp. 96 ～ 101、doi : 10.1007/3-540-45848-4_8、ISBN 978-3-540-43309-5。
エフラット、アロン; エルテン、セシム; コボロフ、スティーブン G. (2007)、「平面グラフの固定位置円弧描画」、グラフアルゴリズムとアプリケーションジャーナル、11 (1): 145–164、doi : 10.7155/jgaa.00140。
Fekete, Jean-Daniel; Wang, David; Dang, Niem; Aris, Aleks; Plaisant, Catherine (2003)、「ツリーマップ上のグラフリンクのオーバーレイ」、IEEE Symp. on Information Visualization、ポスター概要、pp. 82–83。
ギルマン、ジェーン、キーン、リンダ(2002)、「単語シーケンスと交差数」(PDF)、複素多様体と双曲幾何学 (グアナファト、2001)、Contemporary Mathematics、第 311 巻、プロビデンス、ロードアイランド: アメリカ数学協会、pp. 231–249、doi :10.1090/conm/311/05455、ISBN 978-0-8218-2957-8、MR 1940172; セクション 2.4「ファレー図と連分数」を参照
Giordano, Francesco; Liotta, Giuseppe; Mchedlidze, Tamara; Symvonis, Antonios (2007)、「上向き平面有向グラフの上向きトポロジカルブック埋め込みの計算」、アルゴリズムと計算: 第 18 回国際シンポジウム、ISAAC 2007、仙台、日本、2007 年 12 月 17 ～ 19 日、議事録、Lecture Notes in Computer Science、vol. 4835、Springer、pp. 172 ～ 183、doi :10.1007/978-3-540-77120-3_17、ISBN 978-3-540-77118-0。
He, Hongmei; Sýkora, Ondrej; Vrt'o, Imrich (2005)、「2 ページ図面の交差最小化ヒューリスティック」、Electronic Notes in Discrete Mathematics、22 : 527–534、doi :10.1016/j.endm.2005.06.088。
Heer, Jeffrey; Bostock, Michael; Ogievetsky, Vadim (2010)、「視覚化動物園の旅」、Communications of the ACM、53 (6): 59–67、doi : 10.1145/1743546.1743567。
Kabakçıoğlu, A.; Stella, AL (2005 年 11 月)、「崩壊ポリマーに隠されたスケールフリーネットワーク」、Physical Review E、72 (5)、055102(R)、arXiv : cond-mat/0409584、Bibcode :2005PhRvE..72e5102K、doi :10.1103/physreve.72.055102、PMID 16383674、S2CID 29977757
増田純夫；中島一夫;柏原敏信；藤澤敏雄 (1990)、「グラフの線形埋め込みにおける交差最小化」、IEEE Transactions on Computers、39 (1): 124–127、doi :10.1109/12.46286、MR 1032144。
Nagel, Till; Duval, Erik (2013)、「円弧図の視覚的調査」(PDF)、2013 VIS ポスター、IEEE
ニコルソン、TAJ (1968)、「ネットワーク内の交差数を最小化する順列手順」、電気技術者協会紀要、115 :21–26、doi :10.1049/piee.1968.0004、MR 0311416。
Owens, Sean Gabriel; Jankun-Kelly, TJ (2013)、「アメリカンフットボールのシーズンとプレーデータの調査のための視覚化」(PDF)、第 1 回 IEEE VIS スポーツデータ視覚化ワークショップ、IEEE
Pretorius, AJ; van Wijk, JJ (2007)、「セマンティックギャップの解消: ユーザー定義ダイアグラムによる遷移グラフの視覚化」、IEEE Computer Graphics and Applications、27 (5): 58–66、doi :10.1109/MCG.2007.121、PMID 17913025、S2CID 8643133。
Saaty, Thomas L. (1964)、「完全グラフの交差点の最小数」、米国科学アカデミー紀要、52 (3): 688–690、Bibcode :1964PNAS...52..688S、doi : 10.1073/pnas.52.3.688、MR 0166772、PMC 300329、PMID 16591215。
Wattenberg, M. (2002)、「アーク図: 文字列の構造の視覚化」、Proc. IEEE Symposium o nInformation Visualization (INFOVIS 2002)、pp. 110–116、doi :10.1109/INFVIS.2002.1173155、ISBN 0-7695-1751-X、S2CID 881989。

[FOOTNOTENagelDuval2013-1] ナゲル＆デュバル（2013年）。

[FOOTNOTEMasudaNakajimaKashiwabaraFujisawa1990-2] 増田ら（1990）。

[3] Alireza MashaghiとRoland van der Veen、分子回路トポロジー対称性の多項式不変量13(9)、1751（2021）

[4] 本の埋め込みにおけるエッジレイアウトへの半円の応用は、Bernhart & Kainen (1979) によってすでに行われていましたが、円弧図と 2 ページの本の埋め込みとの明確な関連は、Masuda et al. (1990) によるものと思われます。

[FOOTNOTEChungLeightonRosenberg1987-5] チャン、レイトン、ローゼンバーグ（1987年）。

[FOOTNOTEGiordanoLiottaMchedlidzeSymvonis2007-6] ジョルダーノら（2007年）。

[FOOTNOTEBekosKaufmannKobourovSymvonis2013-7] Bekos et al. (2013).

[FOOTNOTECardinalHoffmannKustersTóth2018-8] Cardinal et al. (2018).

[FOOTNOTEEfratErtenKobourov2007-9] エフラット、エルテン、コボロフ（2007年）。

[FOOTNOTECimikowskiMumey2007-10] Cimikowski & Mumey (2007).

[FOOTNOTEGilmanKeen2002-11] ギルマン＆キーン（2002年）。

[12] マシャギ、アリレザ;ファン・ワイク、ローランド・J.タンズ、サンダー J. (2014)。「タンパク質と核酸の回路トポロジー」。構造。22 (9): 1227–1237。土井：10.1016/j.str.2014.06.015。PMID 25126961。

[13] Mugler, Andrew; Tans, Sander J.; Mashaghi, Alireza (2014). 「自己相互作用鎖の回路トポロジー：フォールディングおよびアンフォールディングダイナミクスへの影響」. Phys. Chem. Chem. Phys . 16 (41): 22537–22544. Bibcode :2014PCCP...1622537M. doi :10.1039/C4CP03402C. PMID 25228051.