グラフ描画

グラフ描画は、数学とコンピュータサイエンスの分野であり、幾何学的グラフ理論と情報視覚化の手法を組み合わせて、ソーシャルネットワーク分析、地図作成、言語学、バイオインフォマティクスなどのアプリケーションから生じるグラフの2次元（または場合によっては3次元）の表現を導き出します。^[¹^]

グラフやネットワーク図の図は、グラフの頂点と辺を視覚的に表現したものです。この図はグラフそのものと混同してはいけません。非常に異なるレイアウトが同じグラフに対応することがあります。 ^{[ 2 ]} 抽象的には、どの頂点のペアが辺で接続されているかだけが重要です。しかし、実際には、図の中でのこれらの頂点と辺の配置は、その理解しやすさ、使いやすさ、製造コスト、美観に影響を与えます。^{[ 3 ]}グラフが時間とともに辺の追加や削除によって変化し（動的なグラフ描画）、ユーザーのメンタルマップを維持することが目標である場合、問題はさらに深刻になります。^{[ 4 ]}

図の表記規則

グラフは、頂点が円盤、ボックス、またはテキストラベルで表され、辺がユークリッド平面上の線分、ポリライン、または曲線で表されるノードリンク図として描かれることが多い。^[³^]ノードリンク図は、13世紀の博学者ラモン・リュルの名で出版された14世紀から16世紀の偽リュルの著作に遡ることができる。偽リュルは、形而上学的概念の集合間のすべてのペアワイズの組み合わせを分析するために、完全グラフに対してこの種の図を描いた。 ^[⁵^]

有向グラフの場合、矢印は向きを示すための一般的な図式規則です。^{[ 2 ]}しかし、ユーザー調査では、先細りなどの他の規則の方がこの情報をより効果的に提供することが示されています。^{[ 6 ]}上向き平面描画では、すべての辺が低い頂点から高い頂点に向かっているという規則を使用するため、矢印は不要です。^{[ 7 ]}

ノードリンク図の代替的な表記法には、隣接表現として、円パッキング（頂点は平面上の互いに分離した領域で表され、辺は領域間の隣接関係で表される）、交差表現（頂点は互いに分離していない幾何学的オブジェクトで表され、辺はそれらの交差で表される）、可視性表現（頂点は平面上の領域で表され、辺は互いに遮るもののない視線を持つ領域で表される）、合流図（辺は数学的な線路内の滑らかな曲線として表される）、ファブリック（ノードは水平線、辺は垂直線として表される）^{[ 8 ]} 、およびグラフの隣接行列の可視化などがあります。

品質対策

グラフ描画の美観と使いやすさを客観的に評価する手段を見つけるために、さまざまな品質指標が定義されてきました。^{[ 9 ]}同じグラフのさまざまなレイアウト方法の選択を導くことに加えて、一部のレイアウト方法はこれらの指標を直接最適化しようとします。

描画の交差数とは、互いに交差する辺のペアの数のことです。グラフが平面グラフの場合、辺の交差なしに描画するのが便利な場合が多く、この場合、グラフの描画はグラフの埋め込みを表します。しかし、非平面グラフはアプリケーションで頻繁に発生するため、グラフ描画アルゴリズムは一般的に辺の交差を許容する必要があります。^{[ 10 ]}
図面の面積とは、任意の2つの頂点間の最短距離に対する、その図面の最小境界ボックスのサイズのことです。面積が小さい図面は、面積が大きい図面よりも一般的に好ましいとされています。なぜなら、面積が小さいほど、図面の特徴をより大きく表示でき、結果としてより読みやすくなるからです。境界ボックスの縦横比も重要な要素となる場合があります。
対称表示とは、与えられたグラフ内の対称群を見つけ、可能な限り多くの対称性を表示する図を見つける問題です。レイアウト方法の中には、自動的に対称的な図を生成するものもあれば、入力グラフ内の対称性を見つけて、それを利用して図を作成する描画方法もあります。^{[ 11 ]}
エッジの形状は、視覚的に追跡しやすいように、できるだけ単純であることが重要です。ポリライン図では、エッジの複雑さは曲げの数で測ることができ、多くの手法は、総曲げ数またはエッジあたりの曲げ数を少なくすることを目指しています。同様に、スプライン曲線では、エッジの複雑さは、エッジ上の制御点の数で測ることができます。
一般的に用いられる品質指標には、エッジの長さに関するものが多くあります。一般的には、エッジの総長と各エッジの最大長を最小化することが望ましいとされています。さらに、エッジの長さは大きくばらつくよりも均一である方が望ましい場合もあります。
角度解像度は、グラフ描画における最も鋭い角度の尺度です。グラフの頂点の次数が高い場合、必然的に角度解像度は小さくなりますが、角度解像度は次数の関数によって下限が定められます。^{[ 12 ]}
グラフの傾斜数とは、直線セグメントのエッジ（交差を許容）で描画する際に必要な、異なるエッジ傾斜の最小数です。3次グラフの傾斜数は最大で4ですが、5次のグラフの傾斜数は無制限になる場合があります。4次のグラフの傾斜数が制限されているかどうかは未解決です。^{[ 12 ]}

レイアウト方法

グラフのレイアウト戦略にはさまざまな種類があります。

力ベースのレイアウトシステムでは、グラフ描画ソフトウェアは、バネや分子力学のシステムに関連する物理的なメタファーに基づく力のシステムに従って頂点を連続的に移動させることにより、初期の頂点配置を変更します。通常、これらのシステムは、隣接する頂点間の引力とすべての頂点のペア間の反発力を組み合わせ、エッジの長さが小さく、頂点が十分に離れているレイアウトを探します。これらのシステムは、エネルギー関数の勾配降下法に基づく最小化を実行するか、移動する頂点の速度または加速度に力を直接変換する場合があります。^[¹⁴^]
スペクトルレイアウト法では、グラフの隣接行列から導出されるラプラシアンなどの行列の固有ベクトルを座標として使用します。 ^[¹⁵^]
直交レイアウト法は、グラフのエッジをレイアウトの座標軸に平行に水平または垂直に走らせることができる方法です。これらの方法は元々VLSIおよびPCBレイアウト問題用に設計されましたが、グラフ描画にも適用されています。通常、入力グラフの交点を頂点に置き換えることで平面化し、平面化されたグラフのトポロジー埋め込みを見つけ、曲がりを最小限に抑えるようにエッジの向きを選択し、これらの向きに一貫して頂点を配置し、最後にレイアウト圧縮段階で描画の面積を縮小するという、多段階のアプローチを伴います。^{[ 16 ]}
ツリーレイアウトアルゴリズムは、ツリーに適した、根付きツリーのような構造を示します。多くの場合、「バルーンレイアウト」と呼ばれる手法では、ツリー内の各ノードの子ノードが、ノードを囲む円上に描画され、これらの円の半径はツリーの下位レベルで小さくなるため、円同士が重なることはありません。^[¹⁷^]
階層型グラフ描画法（しばしば杉山式描画と呼ばれる）は、有向非巡回グラフ、またはソフトウェアシステムのモジュール間や関数間の依存関係グラフなど、ほぼ非巡回的なグラフに最適です。これらの方法では、グラフのノードは、コフマン・グラハムアルゴリズムなどの方法を使用して水平方向に階層化され、ほとんどのエッジが1つの階層から次の階層へ下向きになるように配置されます。このステップの後、各階層内のノードは交差が最小になるように配置されます。^{[ 18 ]}

1960年代に遡るレイアウトスタイルであるアークダイアグラム^{[ 19 ]}は、頂点を線上に配置し、エッジは線の上または下に半円として描画したり、複数の半円を連結した滑らかな曲線として描画したりできます。
円形レイアウト法では、グラフの頂点を円上に配置し、交差を減らし、隣接する頂点を互いに近づけるように円周上の頂点の順序を慎重に選択します。エッジは、円の弦として、または円の内側または外側の弧として描画できます。場合によっては、複数の円を使用することもできます。^{[ 20 ]}
優位性描画では、ある頂点が別の頂点から到達可能な場合に限り、その頂点が別の頂点の上、右、またはその両方に位置するように頂点を配置します。このようにして、レイアウトスタイルはグラフの到達可能性関係を視覚的に明らかにします。^{[ 21 ]}

アプリケーション固有のグラフ描画

他の応用分野で生じるグラフおよびグラフ図には、

社会図とは、社会ネットワーク分析ソフトウェアでよく提供される、社会ネットワークの図のことです^[²²^]。
ハッセ図は、部分順序に特化したグラフ描画の一種である^{[ 23 ]}
Dessin d'enfantsは、代数幾何学で使用されるグラフ描画の一種です^{[ 24 ]。}
状態図、有限状態機械のグラフィカル表現^{[ 25 ]}
コンピュータネットワーク図は、コンピュータネットワーク内のノードと接続の図解です^{[ 26 ]}
フローチャートとドラコンチャートは、ノードがアルゴリズムのステップを表し、エッジがステップ間の制御フローを表す図です。
プロジェクトネットワークとは、プロジェクトの活動が完了する時系列順をグラフィカルに示したものである。
データフロー図とは、ノードが情報システムの構成要素を表し、エッジが構成要素間の情報の流れを表す図のことである。
系統樹、タンパク質間相互作用ネットワーク、代謝経路を含むバイオインフォマティクス。^{[ 27 ]}

さらに、電子設計自動化（EDA）における配置と配線の手順は、分散コンピューティングにおける貪欲埋め込みの問題と同様に、グラフ描画と多くの点で類似しており、グラフ描画に関する文献には、EDAに関する文献から借用された結果がいくつか含まれています。しかし、これらの問題にはいくつかの重要な点で違いもあります。たとえば、EDAでは、美観よりも面積の最小化と信号長が重要であり、EDAにおける配線問題では、ネットごとに2つ以上の端子が存在する可能性がありますが、グラフ描画における同様の問題では、一般的に各エッジに対して頂点のペアのみが関係します。