Loading article…
グラフ描画において、グラフ描画の 角度解像度は、描画の共通頂点で交わる任意の 2 つのエッジによって形成される最も鋭い角度です。
プロパティ
頂点次数との関係
Formann ら (1993) は、最大次数dのグラフのすべての直線描画の角度分解能は最大でも 2π/ dであると観察しました。つまり、 v が次数dの頂点である場合、 vに接続する辺はvの周囲の空間を合計角度2πのd個のくさびに分割し、これらのくさびのうち最小のものは角度が最大でも2π/ dでなければなりません。さらに強いて言えば、グラフがd正則である場合、その角度分解能は 未満でなければなりません。これは、これが描画の 凸包上の頂点に対して達成できる最良の分解能であるためです。
グラフの色分けとの関係
Formann ら (1993) が示したように、グラフGの最大角度分解能は正方形G 2の彩度数と密接に関係しており、正方形G 2 とは、 G内の頂点間の距離が最大でも 2 であれば、頂点のペアが辺で接続されている、同じ頂点集合上のグラフです 。G 2 をχ色で着色できる場合、正χ角形の頂点に異なる色を割り当て、 Gの各頂点を同じ色の多角形頂点の近くに配置することで、任意のε > 0 に対してG を角度分解能π/ χ − ε で描画できます。この構成を使用して、最大次数d を持つすべてのグラフの描画は、角度分解能が1/ d 2に比例することを示しました。この制限はほぼ厳密です。確率的方法を使用して、すべての描画が角度分解能 を持つ最大次数dのグラフの存在を証明しました。
最適な図面の存在
Formann ら (1993) は、最大角度解像度を達成する描画を持たないグラフが存在することを示す例を示しました。これらのグラフには、角度解像度が限界値に達することなくその値に向かう傾向のある描画の族があります。具体的には、 任意の ε > 0に対して角度解像度π/3 − εの描画を持つ 11 頂点のグラフを示しましたが、角度解像度が正確にπ/3の描画は持ちません 。
グラフの特別なクラス
木々
すべての木は、各頂点の周囲に辺が等間隔になるように描くことができます。この特性は完全な角度分解能と呼ばれます。さらに、各頂点の周囲に辺を自由に並べ替えることができる場合、交差がなく、すべての辺の長さが単位以上で、描画全体が多項式面積の境界ボックス内に収まるような描画が可能です。ただし、各頂点の周囲の辺の循環順序が問題への入力の一部としてすでに決定されている場合、交差のない完全な角度分解能を達成するには、指数面積が必要になることがあります。[1]
外平面グラフ
外平面グラフでは完全な角度分解能が常に可能であるとは限らない。これは、次数が1より大きい描画の凸包上の頂点は、その周囲に等間隔で入射辺を持つことができないためである。しかし、最大次数dのすべての外平面グラフには、 1/ dに比例する角度分解能を持つ外平面描画が存在する。[2]
平面グラフ
最大次数dの平面グラフの場合、Formann ら (1993) の正方形彩色法では、 1/ dに比例する角度解像度の描画が得られます。これは、平面グラフの正方形の彩色数はdに比例する必要があるためです。より正確には、Wegner は 1977 年に平面グラフの正方形の彩色数は最大で であると予想し、彩色数は最大で であることがわかっています。[3]ただし、この手法で生成される描画は一般に平面ではありません。
いくつかの平面グラフでは、平面直線描画の最適な角度分解能はO(1/ d 3 )であり、ここでd はグラフの次数である。[4]さらに、このような描画では、描画内の最短の辺よりも指数的に長い、非常に長い辺を使用せざるを得ない場合がある。Malitz & Papakostas (1994) は、円充填定理と環補題を使用して、最大次数d を持つすべての平面グラフには、グラフ内の頂点の数とは無関係に、角度分解能が最悪でもdの指数関数である平面描画があることを示した。
計算の複雑さ
最大次数dのグラフが角度分解能2π/ d の描画を持つかどうかを判断することは、 d = 4という特殊な場合であっても NP 困難です。[5]ただし、葉を無限に延長すると平面が凸分割される木の描画や、各境界面が中心対称多角形である平面グラフの描画など、特定の制限された描画クラスでは、最適な角度分解能の描画が多項式時間で見つかる場合があります。[6]
歴史
角度分解能は、Formann ら (1993) によって初めて定義されました。
もともとはグラフの直線描画に対してのみ定義されていたが、後の著者らは、エッジが多角形チェーン、[7]円弧、[8]またはスプライン曲線[9]である描画の角度解像度も研究した。
グラフの角度解像度は、グラフの描画時に交差によって形成される角度である交差解像度と密接に関係しています。特に、RAC描画では、これらの角度がすべて直角、つまり可能な限り最大の交差角度になるように努めます。 [10]
注記
- ^ Duncan et al. (2011); Halupczok & Schulz (2011).
- ^ マリッツとパパコスタス (1994);ガーグとタマッシア (1994)。
- ^ クレイマー＆クレイマー (2008);モロイとサラヴァティプール (2005)。
- ^ ガーグ＆タマシア（1994年）。
- ^ フォーマンら。 (1993);ガーグとタマッシア (1995)。
- ^ カールソン＆エップスタイン（2007）；エップスタイン＆ワートマン（2011）。
- ^ カント (1996);グットヴェンガーとムッツェル (1998)。
- ^ チェンら。 (1999);ダンカンら。 （2011年）。
- ^ ブランデス、シュビナ、タマッシア (2000);フィンケルとタマッシア (2005)。
- ^ ディディモ、イーデス、リオッタ (2009)。
参考文献
- Brandes, Ulrik ; Shubina, Galina; Tamassia, Roberto (2000)、「地理ネットワークの視覚化における角度解像度の向上」、Data Visualization 2000: Proceedings of the Joint Eurographics and IEEE TCVG Symposium on Visualization in Amsterdam, the Netherlands、2000 年 5 月 29 ～ 31 日、doi :10.1007/978-3-7091-6783-0_3、ISBN 9783211835159。
- Carlson, Josiah; Eppstein, David (2007)、「凸面と最適角度を持つ木」、Kaufmann, Michael; Wagner, Dorothea (編)、Proc. 14th Int. Symp. Graph Drawing (GD'06)、LNCS、vol. 4372、Springer-Verlag、pp. 77–88、arXiv : cs.CG/0607113、doi : 10.1007 /978-3-540-70904-6_9、S2CID 12598338。
- Cheng, CC; Duncan, CA; Goodrich, MT ; Kobourov, SG (1999)、「円弧による平面グラフの描画」、グラフ描画、第 7 回国際シンポジウム、GD'99、チェコ共和国シュティリン城、1999 年 9 月 15 ～ 19 日、議事録、コンピュータ サイエンスの講義ノート、第 1731 巻、Springer-Verlag、pp. 117 ～ 126、doi : 10.1007/3-540-46648-7_12。
- Didimo, Walter; Eades, Peter ; Liotta, Giuseppe (2009)、「直角交差によるグラフの描画」、アルゴリズムとデータ構造: 第 11 回国際シンポジウム、WADS 2009、バンフ、カナダ、2009 年 8 月 21 ～ 23 日。議事録、Lecture Notes in Computer Science、vol. 5664、pp. 206 ～ 217、doi :10.1007/978-3-642-03367-4_19。
- Duncan, Christian A.; Eppstein, David ; Goodrich, Michael T .; Kobourov, Stephen G.; Nöllenburg, Martin (2011)、「完全な角度解像度と多項式面積によるツリーの描画」、Brandes, Ulrik; Cornelsen, Sabine (編)、Proc. 18th Int. Symp. Graph Drawing、Lecture Notes in Computer Science、vol. 6502、Springer-Verlag、pp. 183–194、arXiv : 1009.0581、doi :10.1007/978-3-642-18469-7_17。
- Eppstein, D. ; Wortman, K. (2011)、「面対称描画の最適角度解像度」、Journal of Graph Algorithms and Applications、15 (4): 551–564、arXiv : 0907.5474、doi :10.7155/jgaa.00238、S2CID 10356432。
- Finkel, Benjamin; Tamassia, Roberto (2005)、「力指向法による曲線グラフ描画」、Graph Drawing、第 12 回国際シンポジウム、GD 2004、ニューヨーク、ニューヨーク州、米国、2004 年 9 月 29 日～10 月 2 日、改訂選書、Lecture Notes in Computer Science、vol. 3383、Springer-Verlag、pp. 448～453、doi : 10.1007/978-3-540-31843-9_46。
- Formann, M.; Hagerup, T.; Haralambides, J.; Kaufmann, M.; Leighton, FT ; Symvonis, A.; Welzl, E. ; Woeginger, G. (1993)、「高解像度での平面グラフの描画」、SIAM Journal on Computing、22 (5): 1035–1052、doi :10.1137/0222063、MR 1237161。
- Garg, Ashim; Tamassia, Roberto (1994)、「平面描画と角度解像度: アルゴリズムと境界」、アルゴリズム、第 2 回ヨーロッパ シンポジウム、オランダ、ユトレヒト、1994 年 9 月 26 ～ 28 日、議事録、コンピュータ サイエンスの講義ノート、第 855 巻、Springer-Verlag、pp. 12 ～ 23、doi :10.1007/BFb0049393。
- Garg, Ashim; Tamassia, Roberto (1995)、「上向きおよび直線平面性テストの計算複雑性について」、Tamassia, Roberto; Tollis, Ioannis (編)、『Graph Drawing』、Lecture Notes in Computer Science、vol. 894、Springer Berlin / Heidelberg、pp. 286–297、doi : 10.1007/3-540-58950-3_384。
- Gutwenger, Carsten; Mutzel, Petra (1998)、「良好な角度解像度を持つ平面ポリライン描画」、Graph drawing (モントリオール、ケベック州、1998)、Lecture Notes in Comput. Sci.、vol. 1547、ベルリン: Springer、pp. 167–182、doi :10.1007/3-540-37623-2_13、MR 1717450。
- Halupczok, Immanuel、Schulz, André (2011)、「完璧な角度と最適な面積で風船を固定する」、第 19 回グラフ描画国際シンポジウムの議事録。
- Kant, G. (1996)、「標準順序付けを使用した平面グラフの描画」、Algorithmica、16 (1): 4–32、doi :10.1007/s004539900035、hdl : 1874/16676、MR 1394492。
- クレイマー、フロリカ; クレイマー、ホルスト (2008)、「グラフの距離彩色に関する調査」、離散数学、308 (2–3): 422–426、doi :10.1016/j.disc.2006.11.059、MR 2378044。
- マリッツ、セス; パパコスタス、アキレアス (1994)、「平面グラフの角度分解能について」、SIAM Journal on Discrete Mathematics、7 (2): 172–183、doi :10.1137/S0895480193242931、MR 1271989。
- モロイ、マイケル; サラバティプール、モハマド R. (2005)、「平面グラフの平方の彩色数の上限」、Journal of Combinatorial Theory、シリーズ B、94 (2): 189–213、doi :10.1016/j.jctb.2004.12.005、hdl : 1807/9473、MR 2145512。