優位性の描画

座標が到達可能性を示すグラフ

優位性描画は、有向非巡回グラフのグラフ描画の一種で、頂点間の到達可能性関係を視覚的に明確にする手法である。優位性描画では、頂点はユークリッド平面上の異なる点に配置され、頂点vが別の頂点uから到達可能であるためには、頂点vの両方の直交座標がuの座標以上でなければならない。優位性描画の辺は直線セグメントとして描画されるか、場合によっては多角形チェーンとして描画される。^[1]

平面グラフ

推移的に簡約された st平面グラフ、つまり単一のソースと単一のシンクを持ち、両方ともグラフの何らかの埋め込みの外面にある有向非巡回平面グラフには、ドミナンス描画があります。これらの描画を見つけるための左右アルゴリズムは、各頂点のx座標を、 sから始めて右から左の順序で辺を優先順位付けするグラフの深さ優先探索順序での位置に設定し、 y座標を同じ方法で取得されるように設定しますが、左から右の順序で辺を優先順位付けします。一般的なドミナンス描画アルゴリズムには、この座標割り当ての後に、ドミナンス描画の特性を維持しながら、頂点を可能な限り左下に移動させる圧縮フェーズがもう 1 つ含まれています。結果の描画はn × n の整数グリッド内に収まり、基礎となる位相的埋め込みの多くの対称性を表示します。この描画、およびより一般的には推移的に簡約されたst平面グラフのすべてのドミナンス描画は、必然的に平面であり、辺は直線です。^[1]^[2]

推移的に縮小されていないst平面グラフの場合、各辺を細分化することで、同等の推移的に縮小されたグラフを取得できます。ただし、結果として得られる推移的に縮小されたグラフを直線で描画すると、元のグラフの一部の辺が細分によって導入されたダミー頂点で曲がった部分を持つ描画になります。 ^[1]^[2]平面優位の描画は必ずしも上向きの平面描画にはなりません。一部の辺は水平になる場合もありますが、45°回転させると必ず上向きの平面描画になります。^[1] 有向非巡回グラフを描画する他の方法と比較すると、左右アルゴリズム（平面化の前処理ステップを併用）は、生成される描画の面積、曲がりの数、描画のアスペクト比の点では優れたパフォーマンスを発揮しましたが、総辺長の点では劣ることがわかりました。^[3]

非平面グラフ

有向非巡回グラフ（平面性に関わらず）が支配図を持つ場合、到達可能性によって順序付けられたその頂点の半順序集合が2 次元の順序を持つ。推移的に縮約された有向非巡回グラフの（回転した）支配図は、対応する半順序のハッセ図として用いることができる。 ^[4]

共優性

有向非巡回グラフD ₁ = ( V , E ₁ ) の支配描画において、1つの軸の解釈を反転すると、共到達可能性と呼ばれる新しい関係が得られる。つまり、x _a ≥ x _{bかつ y}_a ≤ y _bであれば、点 ( x a , y _a ) は点 ( x _b , y _b₎から共到達可能とみなせる。このように、支配描画は、同じ頂点集合上に2つ目の有向非巡回グラフ D 2 = ( V , E 2 ) を誘導すると考えられる。このような同時表現を単一の描画（到達可能性と共到達可能性の観点から解釈）で可能にする、共有基底集合上の部分順序のペア {≤ 1 _, ≤ 2 }は_、_共支配_的と呼ばれる。^[5]

弱い優位性の描画

到達可能性順序がより高い次元を持つ有向非巡回グラフの場合、弱い支配描画とは、すべての辺が上向き、右向き、または両方向きであるものの、座標的にu がv を支配する頂点ペア ( u、 v ) が存在する描画のことである。グラフ上でv はuから到達できない。頂点uの座標 (u_x、u_y) が頂点vの座標 (v_x、v_y) と等しいかそれ以下である場合、つまり XY 平面でu_x <= v_x かつ u_y <= v_y である場合、頂点uは別の頂点v を支配すると説明した。この描画スタイルの目標は、このような誤って暗示されるパスの数を最小限に抑えることである。^[6]

参考文献

^ abcd Di Battista, Giuseppe; Eades, Peter ; Tamassia, Roberto ; Tollis, Ioannis G. (1998)、「4.7 Dominance Drawings」、Graph Drawing: Algorithms for the Visualization of Graphs、Prentice Hall、pp. 112– 127、ISBN 978-0-13-301615-4。
^ ab Di Battista, Giuseppe; Tamassia, Roberto ; Tollis, Ioannis G. (1992)、「平面上向き描画の面積要件と対称性表示」、Discrete and Computational Geometry、7 (4): 381– 401、doi : 10.1007/BF02187850、MR 1148953。
^ ディ・バッティスタ、ジュゼッペ;ガーグ、アシム。リオッタ、ジュゼッペ。パリセ、アルマンド。ロベルト・タマシア;タッシナリ、エマヌエーレ。ヴァルギウ、フランチェスコ。 Vismara、Luca (2000)、「有向非環状グラフの描画: 実験的研究」、International Journal of Computational Geometry & Applications、10 (6): 623–648、doi :10.1142/S0218195900000358、MR 1808215 。
^ ベイカー, KA;フィッシュバーン, PC ;ロバーツ, FS (1972)、「2次元の部分順序」、ネットワーク、2 (1): 11– 28、doi :10.1002/net.3230020103 。
^ Tanenbaum, Paul J.; Whitesides, Sue (1996)、「複数ポセットの同時優位性表現」（PDF）、Order、13 (4): 351– 364、doi :10.1007/bf00405594、S2CID 121516733 。
^ Kornaropoulos, Evgenios M.; Tollis, Ioannis G. (2013), "Weak dominance drawing for directed acyclic graphs", Didimo, Walter; Patrignani, Maurizio (eds.), Graph Drawing: 20th International Symposium, GD 2012, Redmond, WA, USA, September 19-21, 2012, Revised Selected Papers , Lecture Notes in Computer Science, vol. 7704, Springer, pp. 559– 560, doi : 10.1007/978-3-642-36763-2_52。

[dett98-1] Di Battista, Giuseppe; Eades, Peter ; Tamassia, Roberto ; Tollis, Ioannis G. (1998)、「4.7 Dominance Drawings」、Graph Drawing: Algorithms for the Visualization of Graphs、Prentice Hall、pp. 112– 127、ISBN 978-0-13-301615-4。

[dtt92-2] Di Battista, Giuseppe; Tamassia, Roberto ; Tollis, Ioannis G. (1992)、「平面上向き描画の面積要件と対称性表示」、Discrete and Computational Geometry、7 (4): 381– 401、doi : 10.1007/BF02187850、MR 1148953。

[dgl+00-3] ディ・バッティスタ、ジュゼッペ;ガーグ、アシム。リオッタ、ジュゼッペ。パリセ、アルマンド。ロベルト・タマシア;タッシナリ、エマヌエーレ。ヴァルギウ、フランチェスコ。 Vismara、Luca (2000)、「有向非環状グラフの描画: 実験的研究」、International Journal of Computational Geometry & Applications、10 (6): 623–648、doi :10.1142/S0218195900000358、MR 1808215 。

[bfr72-4] ベイカー, KA;フィッシュバーン, PC ;ロバーツ, FS (1972)、「2次元の部分順序」、ネットワーク、2 (1): 11– 28、doi :10.1002/net.3230020103 。

[tw96-5] Tanenbaum, Paul J.; Whitesides, Sue (1996)、「複数ポセットの同時優位性表現」（PDF）、Order、13 (4): 351– 364、doi :10.1007/bf00405594、S2CID 121516733 。

[kt13-6] Kornaropoulos, Evgenios M.; Tollis, Ioannis G. (2013), "Weak dominance drawing for directed acyclic graphs", Didimo, Walter; Patrignani, Maurizio (eds.), Graph Drawing: 20th International Symposium, GD 2012, Redmond, WA, USA, September 19-21, 2012, Revised Selected Papers , Lecture Notes in Computer Science, vol. 7704, Springer, pp. 559– 560, doi : 10.1007/978-3-642-36763-2_52。