上向き平面描画

グラフ描画において、有向非巡回グラフの上向き平面描画は、グラフをユークリッド平面に埋め込むことであり、その場合、辺は交差しない単調な上向き曲線として表される。つまり、各辺を表す曲線は、すべての水平線が最大でも1点で交差し、2つの辺は共有の端点以外で交差してはならないという特性を持つべきである。^[1]この意味で、これは階層化グラフ描画、つまり辺が交差する可能性のある単調曲線であるが、交差は最小限に抑えられるグラフ描画のスタイルにとって理想的なケースである。

有向非巡回グラフは上向き平面描画を持つためには平面でなければならないが、すべての平面非巡回グラフがそのような描画を持つわけではない。単一のソース（入ってくる辺のない頂点）とシンク（出ていく辺のない頂点）を持つ平面有向非巡回グラフのうち、上向き平面描画を持つグラフはst -平面グラフ、つまりソースとシンクの両方がグラフの少なくとも 1 つの平面埋め込みの同じ面に属する平面グラフである。より一般的には、グラフG が上向き平面描画を持つのは、それが有向かつ非巡回であり、同じ頂点セット上のst -平面グラフのサブグラフである場合に限ります。 ^[2]

上向きの埋め込みでは、各頂点に入力されるエッジと出力されるエッジのセットは、頂点でのエッジの循環順序で連続しています。与えられた有向非巡回グラフの平面埋め込みは、この特性を持つ場合、二峰性があると言われています。さらに、与えられた頂点で同じ向きの 2 つの連続するエッジ間の角度は、π より小さい場合は小さい、π より大きい場合は大きいとラベル付けできます。各ソースまたはシンクは、必ず 1 つの大きな角度を持つ必要があり、ソースでもシンクでもない各頂点には大きな角度がまったくありません。さらに、描画の各内部面には、大きな角度よりも 2 つ多い小さな角度があり、外部面には、小さな角度よりも 2 つ多い大きな角度がある必要があります。一貫した割り当ては、これらの特性を満たす角度のラベル付けです。すべての上向きの埋め込みには、一貫した割り当てがあります。逆に、一貫した割り当てを持つ二峰性の平面埋め込みを持つすべての有向非巡回グラフには、線形時間で構築できる上向きの平面描画があります。^[3]

単一のソースを持つグラフでは、別の特徴付けが可能です。この場合、上向きの平面埋め込みは、ソースが外面にある必要があり、グラフのすべての無向サイクルには、サイクルのエッジの両方が入来する頂点が少なくとも1つなければなりません（たとえば、図で最も高い位置にある頂点）。逆に、埋め込みがこれらのプロパティの両方を持っている場合、それは上向きの埋め込みと同等です。^[4]

上向き平面性テストのいくつかの特殊なケースは多項式時間で実行可能であることが知られています。

• グラフがst平面であるかどうかをテストすることは、 sからtへの辺を追加し、残りのグラフが平面であるかどうかをテストすることで線形時間で達成できます。同様に、単一のソースとシンクを持つ有向非巡回グラフの上向きの平面描画（存在する場合）を線形時間で構築することができます。^[5]
• 固定された平面埋め込みを持つ有向グラフが、与えられた埋め込みと一致する埋め込みで上向き平面に描画できるかどうかをテストするには、埋め込みが双峰性であることを確認し、一貫性のある割り当て問題をネットワークフロー問題としてモデル化します。実行時間は入力グラフのサイズに比例し、ソースとシンクの数に比例します。^[6]
• 有向多面体グラフは一意の平面埋め込みを持つため、これらのグラフの上向き平面描画の存在は多項式時間でテストできる。^[7]
• 外平面有向非巡回グラフが上向き平面描画を持つかどうかをテストすることも多項式である。 ^[8]
• すべての直列並列グラフは、直列並列構造と一貫して向きが定められており、上向き平面状である。上向き平面図は、グラフの直列並列分解から直接構築することができる。^[9]より一般的には、無向直列並列グラフの任意の向きは、多項式時間で上向き平面性をテストすることができる。^[10]
• あらゆる方向を向いた木は上向きの平面である。^[9]
• 二部平面グラフは、その辺が二部分割の一方から他方へ一貫して向いている場合、上向き平面グラフである^{[9] [11]。}
• より複雑な多項式時間アルゴリズムは、単一のソースと複数のシンクを持つグラフの上方平面性をテストするために知られている（またはその逆）。^[12]
• 上向き平面性のテストは、三連結成分とカット頂点の数が一定であれば多項式時間で実行でき、これら2つの数に対して固定パラメータで処理可能です。 ^[13]また、入力グラフのサイクロマティック数に対しても固定パラメータで処理可能です。 ^{[14]また、}ソース数（つまり、入辺のない頂点）に対しても固定パラメータで処理可能です。 ^[15]
• すべての頂点のy座標が固定されている場合、描画を上向きに平面にするx座標の選択は多項式時間で見つけることができます。 ^[16]

しかし、複数のソースとシンクを持つ平面有向非巡回グラフが上向き平面描画を持つかどうかを判断することはNP完全である。 ^[17]

ファリーの定理によれば、すべての平面グラフには、その辺が直線セグメントで表現される描画があり、上向き平面描画についても同じことが言える。つまり、すべての上向き平面グラフには、直線上向き平面描画がある。^[18]推移的に縮小された st平面グラフ の直線上向き描画は、優位描画の手法によって得ることができ、すべての頂点はn  ×  nグリッド内で整数座標を持つ。^[19]ただし、他の特定の上向き平面グラフでは、すべての直線上向き平面描画で指数面積が必要になる場合があります。 ^[18]埋め込みの選択が固定されている場合、有向直列並列グラフや有向木でも指数面積が必要になる場合があります。^[20]

上向きの平面描画は、半順序集合のハッセ図にとって特に重要である。なぜなら、これらの図は通常、上向きに描画する必要があるからである。グラフ理論的には、これらは推移的に縮小された有向非巡回グラフに対応する。そのようなグラフは半順序の被覆関係から形成され、半順序自体はグラフの到達可能性関係を形成する。半順序集合が 1 つの最小要素を持ち、 1 つの最大要素を持ち、上向きの平面描画を持つ場合、必然的に格子、つまりすべての要素のペアが一意の最大下限と一意の最小上限を持つ集合を形成する。^[21]格子のハッセ図が平面であるための必要条件は、その順序次元が最大で 2 である場合である。^[22]ただし、次元が 2 で、最小要素と最大要素が 1 つである一部の半順序は、上向きの平面描画を持たない ( の推移閉包によって定義された順序を取る)。 ${\displaystyle a<b,a<c,b<d,b<e,c<d,c<e,d<f,e<f}$

脚注

調査と教科書

研究論文