レイヤーグラフ描画

階層グラフ描画または階層グラフ描画は、有向グラフの頂点を水平方向の行または層に描画し、辺を一般的に下向きにするグラフ描画の一種です。 ^{[ 1 ] [ 2 ] [ 3 ]}この描画スタイルを最初に開発した杉山耕造にちなんで、杉山式グラフ描画とも呼ばれています。^{[ 4 ]}

階層型描画の理想的な形式は、すべての辺が一様に配向され、辺同士が交差しない上向き平面描画です。しかし、グラフにはサイクルが含まれることが多く、一様に配向されていない辺の数を最小化することはNP困難であり、交差の数を最小化することもNP困難です。そのため、階層型グラフ描画システムでは、通常、一連のヒューリスティックを適用して、描画におけるこれらの欠陥を減らしますが、欠陥の数が最小となる描画を見つけることを保証するものではありません。

階層型グラフ描画の作成は、以下の手順で進められます。

• 入力グラフが有向非巡回グラフでない場合、反転することで非巡回グラフになるエッジの集合が特定されます。最小のエッジの集合を見つけることはNP完全なフィードバックアーク集合問題であるため、ここでは厳密な最適化アルゴリズムの代わりに貪欲なヒューリスティックがよく使用されます。 ^{[ 1 ] [ 2 ] [ 3 ] [ 5 ] [ 6 ] [ 7 ]}この問題の厳密な解は整数計画法を使用して定式化できます。^{[ 3 ]}あるいは、反転するエッジの数が非常に少ない場合は、固定パラメータ追跡可能なアルゴリズムでこれらのエッジを見つけることができます。^{[ 8 ]}
• 最初のステップで得られた有向非巡回グラフの頂点は、各エッジが上位の層から下位の層へ向かうように、層に割り当てられます。この段階の目標は、少数の層、多数の層にまたがる少数のエッジ、および層への頂点の均等な割り当てを同時に生成することです。^{[ 1 ] [ 2 ] [ 3 ]}例えば、ミルスキーの定理により、各頂点から始まる最長パスの長さに応じて頂点を層に割り当てると、可能な限り最小の層数を持つ割り当てが生成されます。^{[ 1 ] [ 3 ]}コフマン・グラハムアルゴリズムは、層ごとの頂点数に予め定められた制限があり、その制約の下で層数を近似的に最小化するレイヤリングを見つけるために使用できます。^{[ 1 ] [ 2 ] [ 3 ]}最も幅の広い層の幅を最小化することはNP困難ですが、分岐限定法またはヒューリスティックに近似することで解決できます。^{[ 3 ]}あるいは、エッジによって張られる層の総数を最小化する問題（各層の頂点数に制限なし）は、線形計画法を用いて解くことができる。^{[ 9 ]}整数計画法は、より時間がかかるものの、エッジ長の最小化と各レベルの頂点数の制限を組み合わせるために使用できる。^{[ 10 ]}
• 複数のレイヤーにまたがるエッジはダミー頂点のパスに置き換えられ、このステップの後、拡張されたグラフの各エッジは、描画の隣接するレイヤー上の 2 つの頂点を接続するようになります。^{[ 1 ] [ 2 ]}
• オプションの手順として、既存の 2 つの頂点層の間にエッジ集中頂点 (または合流接合部) の層を挿入し、これらのエッジ集中部を介して完全な二部グラフをスターに置き換えることでエッジ密度を低減することができます。^{[ 3 ] [ 11 ] [ 12 ]}
• 各層内の頂点は、前の層に接続するエッジ間の交差数を減らすために順列されます。 ^{[ 1 ] [ 2 ] [ 3 ]}最小の交差数を見つけるか、最大の交差のないエッジのセットを見つけることは、このように一度に 1 つの層を順序付ける場合でも NP 完全です。^{[ 13 ] [ 14 ]}そのため、ここでもヒューリスティックに頼るのが一般的です。たとえば、各頂点を前のレベルの隣接頂点の位置の平均または中央値を見つけて決定された位置に配置し、交差数が改善される限り隣接するペアを交換するなどです。^{[ 1 ] [ 2 ] [ 9 ] [ 14 ] [ 15 ]}あるいは、一度に 1 つの層の頂点の順序は、その層と前の層との間の交差数に関して固定パラメータ扱いやすいアルゴリズムを使用して選択できます。 ^{[ 3 ] [ 16 ]}
• 各頂点には、前のステップで計算された順列と一致する、そのレイヤー内の座標が割り当てられます。^{[ 1 ] [ 2 ]}このステップでの考慮事項には、不要な曲がりを防ぐために、2 つの隣接ノード間の線上にダミーノードを配置すること、および各頂点を隣接ノードに対して中心位置に配置することが含まれます。^{[ 3 ]}杉山の元の研究では、このステップの二次計画法による定式化が提案されました。後の Brandes と Köpf の方法では、線形時間で実行でき、エッジごとに最大 2 つの曲がりを保証します。^{[ 3 ] [ 17 ]}
• アルゴリズムの最初のステップで反転されたエッジは元の向きに戻され、ダミー頂点はグラフから削除され、頂点とエッジが描画されます。頂点とエッジの交差を避けるために、描画の複数のレイヤーにまたがるエッジは、エッジに沿ってダミー頂点に割り当てられた各位置を通過する多角形のチェーンまたはスプライン曲線として描画される場合があります。 ^{[ 1 ] [ 2 ] [ 9 ]}

最も単純な形式では、階層型グラフ描画アルゴリズムは、作成されるダミー頂点の数が多いため、 n個の頂点とm個のエッジを持つグラフではO( mn ) の時間が必要になる場合があります。しかし、アルゴリズムのいくつかのバリアントでは、ダミー頂点を明示的に構築することなくその効果をシミュレートすることが可能で、ほぼ線形時間の実装につながります。^{[ 18 ]}

Graphvizの「ドット」ツールは、レイヤー化された図を生成します。^{[ 9 ]}レイヤー化されたグラフ描画アルゴリズムは、Microsoft Automatic Graph Layout ^{[ 19 ]}およびTulip ^{[ 20 ]}にも含まれています。

階層型グラフ描画アルゴリズムは、通常は頂点を行に、辺を上から下に描画しますが、代わりに頂点を列に、辺を左から右に描画することもできます。^{[ 21 ]同じアルゴリズムフレームワークは、グラフが何らかの開始ノードの周りの同心円状に配置された放射状レイアウト[ 3 ] [ 22 ]}や、グラフの3次元階層型描画にも適用されています。 ^{[ 3 ] [ 23 ]}

長い辺が多い階層グラフの描画では、辺のセットを束にまとめて同じダミー頂点のセットを通してルーティングすることで、辺の混雑を軽減できます。^{[ 24 ]}同様に、連続するレイヤーのペア間で多くの辺が交差する描画では、最大二部グラフの辺を合流束にまとめることができます。^{[ 25 ]}

頂点が層状に配置された図は、杉山のフレームワークに従わないアルゴリズムによって構築される可能性がある。例えば、この種の図を持つグラフはパス幅が制限されているという事実を利用することで、無向グラフがh層を使用して最大k個の交差を持つ図を持っているかどうかを、 kとhの任意の固定選択に対して多項式時間で判定することが可能である。^{[ 26 ]}

概念格子の階層的描画には、杉山のフレームワークと加算法（各頂点が集合を表し、頂点の位置が集合の要素を表すベクトルの合計である）を組み合わせたハイブリッドアプローチが使用されることがある。このハイブリッドアプローチでは、アルゴリズムの頂点置換と座標割り当てフェーズが、各頂点の水平位置をその頂点の要素を表すスカラーの合計として選択する単一のフェーズに置き換えられる。^{[ 27 ]}階層的グラフ描画法は、力指向型グラフ描画アルゴリズム の初期配置を提供するためにも使用されている。^{[ 28 ]}