Loading article…
同時埋め込みは、グラフ描画および情報可視化における手法であり、2 つ以上の異なるグラフを、同じまたは重複するラベル付き頂点の集合上に可視化し、両方のグラフ内で交差を回避します。一方のグラフのエッジと他方のグラフのエッジ間の交差は許可されます。 [ 1 ]
辺をポリラインまたは曲線として描画することが許される場合、任意の平面グラフは、その頂点が平面上の任意の位置にある状態で交差することなく描画でき、同じ頂点配置によって同時埋め込みが実現される。[ 1 ]
制限付きモデルには 2 つあります。1 つは同時幾何学的埋め込みで、各グラフはより複雑な曲線ではなく線分でエッジを表す平面上に描画する必要があり、与えられた 2 つのグラフは平面グラフのサブクラスに制限されます。もう 1 つは固定エッジによる同時埋め込みで、エッジに曲線や曲がりが許容されますが、両方のグラフの任意のエッジは両方の図で同じ曲線で表現されなければなりません。[ 1 ] 制限なしモデルでは、任意の 2 つの平面グラフが同時埋め込みを持つことができます。
同時埋め込みは、グラフ描画および情報可視化における手法であり、2 つ以上の異なるグラフを、同じまたは重複するラベル付き頂点の集合上に可視化し、両方のグラフ内で交差を回避します。一方のグラフのエッジと他方のグラフのエッジ間の交差は許可されますが、同じグラフの 2 つのエッジ間の交差は許可されません。[ 1 ]
辺をポリラインまたは曲線として描画することが許される場合、任意の平面グラフは、頂点が平面上の任意の位置にある状態で交差なく描画できます。2 つのグラフに同じ頂点配置を使用すると、2 つのグラフを同時に埋め込むことができます。研究は、曲がりが少ない、または 2 つのグラフの辺間の交差が少ない描画を見つけることに集中しています。[ 1 ]
制約付きモデルは 2 つあります。同時幾何学的埋め込みと固定エッジによる同時埋め込みです。固定エッジによる同時埋め込みでは、エッジに曲線や曲がりが許容されますが、両方のグラフに存在するエッジは、両方の図で同じ曲線で表現されなければなりません。同時幾何学的埋め込みが存在する場合、それは自動的に固定エッジによる同時埋め込みでもあります。[ 1 ]
2 つ以上のグラフに対する同時埋め込み問題では、入力グラフのすべてのペアが互いに同じ交差を持つ、つまりグラフのエッジと頂点の集合がヒマワリを形成すると仮定するのが一般的です。この制約はヒマワリ交差として知られています。[ 1 ]
同時埋め込みは、与えられたグラフのすべてのエッジを覆うことができる平面部分グラフの最小数である厚さと、同じ色のエッジが交差しない与えられたグラフの直線描画に必要なエッジ色の最小数である幾何学的厚さに密接に関連しています。特に、与えられたグラフのエッジを同時埋め込みを持つ 2 つの部分グラフに分割できる場合、そのグラフの厚さは 2 であり、エッジを同時幾何学的埋め込みを持つ 2 つの部分グラフに分割できる場合、幾何学的厚さは 2 です。[ 2 ]
同時幾何学的埋め込みでは、各グラフは、より複雑な曲線ではなく、エッジを線分で表した平面グラフとして描画する必要があり、与えられた 2 つのグラフは平面グラフのサブクラスに制限されます。同時幾何学的埋め込みに関する多くの結果は、与えられた 2 つのグラフの頂点のデカルト座標が、2 つのグラフの特性から導出できるという考えに基づいています。この種の最も基本的な結果の 1 つは、同じ頂点集合上の任意の2 つのパス グラフは常に同時埋め込みを持つという事実です。このような埋め込みを見つけるには、最初のパスの頂点の位置をx座標として、2 番目のパスの同じ頂点の位置をy座標として使用できます。このようにして、最初のパスは自動的に自己交差しないタイプの曲線であるx単調ポリラインとして描画され、2 番目のパスも同様にy単調ポリラインとして描画されます。
このタイプの描画では、頂点をグラフのサイズに比例する次元の整数格子に配置します。同様に定義されたレイアウトは、両方のグラフがキャタピラグラフである場合、または両方ともサイクルグラフである場合にも機能しますが、グリッドサイズは大きくなりますが、依然として線形です。線形次元のグリッドへの同時埋め込みは、すべてのグラフがスターグラフである場合にも可能です。常に同時埋め込みが可能であるが、より大きなグリッドサイズが必要になる可能性のある他のグラフタイプのペアには、ホイールグラフとサイクルグラフ、木とマッチング、または最大次数が 2であるグラフのペアが含まれます。ただし、平面グラフとマッチング、または Angelini、Geyer、Neuwirth、Kaufmann のペアでは、同時幾何学的埋め込みが不可能な木とパスが存在することが示されました。[ 3 ] [ 4 ]
2 つのグラフが同時幾何学的埋め込みを許容するかどうかをテストすることはNP 困難です。[ 1 ] [ 5 ]より正確には、実数の存在理論に対して完全です。この結果の証明は、同時幾何学的埋め込みを持つグラフのペアによっては、それらを描画できる最小のグリッドのサイズが 2 倍指数関数的であることを意味します。[ 6 ] [ 2 ] 同時幾何学的埋め込みが存在する場合、それは自動的に固定エッジを持つ同時埋め込みでもあります。[ 1 ]
固定エッジによる同時埋め込みでは、エッジに曲線や曲がりが許容されますが、両方のグラフに存在するエッジは、両方の図で同じ曲線で表現されなければなりません。[ 1 ]異なるタイプの入力が常に埋め込みを持つか、場合によっては不可能かの分類は、描画する 2 種類のグラフだけでなく、それらの交差の構造にも依存します。たとえば、与えられた 2 つのグラフが両方とも外平面グラフであり、それらの交差が線形フォレストであり、エッジごとに最大 1 つの曲がりがあり、頂点座標と曲がり点がすべて多項式面積のグリッドに属している場合、常にそのような埋め込みを見つけることができます。ただし、そのような埋め込みを持たない、より複雑な交差を持つ他の外平面グラフのペアも存在します。また、平面グラフと木の任意のペアに対して、固定エッジによる同時埋め込みを見つけることもできます。[ 7 ] [ 8 ] [ 9 ]
与えられた 2 つのグラフに対して固定エッジを持つ同時埋め込みの存在を多項式時間でテストできるかどうかは未解決の問題です。ただし、3 つ以上のグラフの場合、この問題はNP 完全です。固定エッジを持つ同時埋め込みが存在する場合、それらは外平面グラフのペア、および双連結グラフ、つまり交差が双連結であるグラフのペアに対して多項式時間で見つけることができます。[ 1 ] [ 10 ] [ 11 ] [ 12 ]
任意の 2 つの平面グラフは同時埋め込みが可能です。これは、辺ごとに最大 2 つの曲がりを持つ多項式面積のグリッドで行うことができます。任意の 2 つのサブハミルトングラフは、辺ごとに最大 1 つの曲がりを持つ同時埋め込みが可能です。[ 1 ] [ 8 ] [ 13 ]