円形レイアウト

グラフ描画において、円形レイアウトは、グラフの頂点を円上に配置し、多くの場合、正多角形の頂点を形成するように均等間隔で配置する描画スタイルです。

円形レイアウトは、スターネットワークやリングネットワークなどの通信ネットワークトポロジーに適しています。^[1]また、代謝ネットワーク の循環部分にも適しています。^[2]ハミルトンサイクルが既知のグラフの場合、円形レイアウトによりサイクルを円として表すことができます。このように、円形レイアウトはハミルトン立方グラフのLCF表記の基礎となります。^[3]

円形レイアウトは、グラフ全体の描画に単独で使用できますが、二重連結コンポーネント^[4]、遺伝子相互作用グラフ内の遺伝子のクラスター^{[5] 、または}ソーシャルネットワーク内の自然なサブグループ^[6]など、より大きなグラフ描画内の頂点の小さなクラスターのレイアウトとして使用することもできます。複数の頂点の円がこのように使用される場合、力指向グラフ描画などの他の方法を使用してクラスターを配置することができます。^[7]

バイオインフォマティクスやソーシャルネットワークの視覚化などのアプリケーションにおける円形レイアウトの利点の1つは、その中立性です。^[8]すべての頂点を互いに等距離に配置し、図面の中心から等距離に配置することで、どの頂点にも特権的な位置が与えられず、中心に位置するノードがより重要であると視聴者が認識する傾向に対抗します。^[9]

図面の辺は、円の弦として描かれる場合もあれば、 ^[10]円弧として描かれる場合もあり、 ^{[11] （頂点円に垂直な場合もあり、その場合、辺は双曲}幾何学のポアンカレ円板モデルの線をモデル化します）、または他の種類の曲線として描かれる場合もあります。^[12]

円形レイアウトにおける頂点円の内側と外側の視覚的な区別は、2つの異なるエッジ描画スタイルを区別するために使用できます。たとえば、Gansner & Koren (2007) の円形描画アルゴリズムでは、円内のエッジの束ね方と、束ねられていない一部のエッジを円の外側に描画します。^[12]

正則グラフの円形レイアウトでは、内側と外側の両方のエッジが円弧として描かれ、これらの円弧の1つと頂点円の入射角は円弧の両端で同じであり、この特性により描画の角度解像度の最適化が簡素化されます。^[11]

複数の著者が、すべての辺が頂点円の内側に描かれているときに、辺の交差数を最小化する円形レイアウトの頂点の順列を見つける問題を研究してきました。この交差数は、外平面グラフの場合のみゼロになります。^[13]他のグラフの場合、これらのコンポーネントは相互作用しないように描かれる可能性があるため、ソリューションを組み合わせる前に、グラフの各2連結コンポーネントごとに個別に最適化または削減することができます。 ^[14]一般に、交差数を最小化することはNP完全です。^[15]

Shahrokhi ら (1995) は、バランスのとれたカットまたはエッジ セパレータに基づく近似アルゴリズムを説明しました。バランスのとれたカットは、いくつかのエッジのサブセットであり、これらのエッジを削除すると、与えられたグラフがほぼ等しい数の頂点を持つ 2 つのサブグラフに分離されます。近似カットを見つけた後、彼らのアルゴリズムは、カットを横切るエッジによって形成される追加の交差を考慮せずに、カットの両側に 2 つのサブグラフを再帰的に配置します。彼らは、頂点 を持つグラフ上の結果のレイアウトで発生する交差の数が であることを証明しています。 ここで、 は交差の最適数であり、 はこのレイアウト方法で使用されるバランスのとれたカット アルゴリズムの近似比です。^[16]彼らの研究では、を主張した 1994 年のFan ChungとShing-Tung Yauの論文を引用していますが、これは後に誤った証明であることが判明しました。^[17]代わりに、バランスカット問題に対する既知の最良の近似値は であり、^[18]この円形レイアウトアルゴリズムは、頂点次数に比べて交差数が多いグラフ上での近似比を実現します。 ${\displaystyle G}$${\displaystyle n}$$${\displaystyle O{\Bigl (}{\bigl (}\rho \log n{\bigr )}^{2}\cdot {\bigl (}C+\sum _{v\in V(G)}\deg(v)^{2}{\bigr )}{\Bigr )},}$$${\displaystyle C}$${\displaystyle \rho}$${\displaystyle \rho =O(1)}$${\displaystyle \rho =O({\sqrt {\log n}})}$${\displaystyle O(\log^{3}n)}$

交差の複雑さを軽減するためのヒューリスティックな方法も考案されており、例えば、慎重な頂点挿入順序と局所最適化に基づいています。^[19]円形レイアウトを使用して交差の数を最大化することもできます。特に、頂点のランダムな順列を選択すると、各交差が確率 1/3 で発生するため、予想される交差数は、すべての可能なレイアウトの最大交差数の 3 倍以内になります。 この方法を非ランダム化すると、近似比3の決定論的 近似アルゴリズムが得られます。 ^[20]

交差問題に加えて、円形レイアウトにおける辺の長さ、交差の角度分解能、カット幅（円の1つの弧を反対の弧に接続する辺の最大数）を最適化する問題の円形バージョンも検討されてきたが^[21]、これらの問題の多くはNP完全である。^[22]

• コードダイアグラム（情報視覚化）は、情報視覚化と密接に関連する概念です。
• 平面性、ランダムな円形のレイアウトから始めて、平面グラフの描画を解くために頂点を移動する必要があるパズル。

• Graphvizの円形レイアウトエンジン