Loading article…
グラフ理論において、st平面グラフは、平面グラフの双極方向であり、方向のソースとシンクの両方がグラフの外面上にある。つまり、平面上で交差せずに描かれた有向グラフであり、グラフには有向サイクルがなく、グラフの頂点の 1 つにだけ入力辺がなく、グラフの頂点の 1 つにだけ出力辺がなく、これら 2 つの特別な頂点は両方ともグラフの外面にある。[1]
描画内では、グラフの各面は同じ構造を持つ必要があります。つまり、面のソースとして機能する頂点が 1 つ、面のシンクとして機能する頂点が 1 つあり、面内のすべてのエッジはソースからシンクへの 2 つのパスに沿って方向付けられます。st 平面グラフのシンクからソースに戻り、外側の面を通って追加のエッジを描画し、次にデュアル グラフを構築すると (各デュアル エッジをそのプライマリ エッジに対して時計回りに向ける)、結果は再びst平面グラフになり、同じように追加のエッジが拡張されます。[1]
秩序理論
これらのグラフは、半順序集合および格子と密接に関連している。半順序集合のハッセ図は、頂点が集合要素である有向非巡回グラフであり、半順序においてx ≤ yであるがx ≤ y ≤ zとなるzが存在しない要素の各ペアx、yに対して、 xからyへの辺が存在する。半順序集合が完全格子を形成するのは、すべての要素のサブセットが一意の最大下限と一意の最小上限を持ち、半順序集合の順序次元が、与えられた半順序が交差する同じ要素セット上の全順序数の最小値である場合に限る。st平面グラフの頂点が到達可能性によって部分的に順序付けられている場合、この順序付けは常に 2 次元完全格子を形成し、そのハッセ図は与えられたグラフの推移的縮約となる。逆に、すべての 2 次元完全格子のハッセ図は常にst平面グラフである。[2]
グラフ描画
この二次元半順序特性に基づいて、すべてのst平面グラフには優位描画を与えることができ、そこでは、すべての 2 つの頂点uとvに対して、 uの両方の座標が対応するvの座標よりも小さい 場合に限り、uからvへのパスが存在する。[3]このような描画の座標は、st平面グラフの 1 つの頂点がクエリごとに一定時間で別の頂点に到達できるかどうかをテストするために使用できるデータ構造として使用することもできます。このような描画を 45° 回転すると、グラフの上向きの平面描画が得られます。有向非巡回グラフGは、 G がst平面グラフのサブグラフである場合に限り、上向きの平面描画を持ちます。[4]
参考文献
- ^ ab Di Battista, Giuseppe; Eades, Peter ; Tamassia, Roberto ; Tollis, Ioannis G. (1998)、「4.2 平面非巡回有向グラフの特性」、Graph Drawing: Algorithms for the Visualization of Graphs、Prentice Hall、pp. 89–96、ISBN 978-0-13-301615-4。
- ^ Platt, CR (1976)、「平面格子と平面グラフ」、Journal of Combinatorial Theory、Ser. B、21 (1): 30–39、doi :10.1016/0095-8956(76)90024-1。
- ^ ディ・バティスタら。 (1998)、4.7 支配的な図面、112 ～ 127 ページ。
- ^ ディ・バティスタ、ジュゼッペ、タマシア、ロベルト（1988）、「非巡回有向グラフの平面表現のアルゴリズム」、理論計算機科学、61（2–3）：175–198、doi：10.1016/0304-3975（88）90123-5。