Loading article…
グラフ描画では、描画に使用される領域がその品質を測定する一般的な方法です。
意味
頂点が整数格子上に配置される描画スタイルの場合、描画の面積は、描画の軸に沿った最小の境界ボックスの面積として定義できます。つまり、 2つの頂点のx座標の最大差とy座標の最大差の積です。頂点がより自由に配置される他の描画スタイルの場合、最も近い頂点のペアが互いに1の距離を持つように描画を拡大縮小し、その後、面積を描画の最小の境界ボックスの面積として再び定義できます。または、面積は、適切な拡大縮小を行った後、描画の凸包の面積として定義できます。 [1]
多項式境界
n頂点を持つ平面グラフの直線描画の場合、描画面積の最適な最悪境界は Θ( n 2 ) である。入れ子になった三角形のグラフは、どのように埋め込まれているかに関係なくこのくらいの面積が必要であり[2]、最大でも面積の 2 乗で平面グラフを描画できる方法がいくつか知られている。[3] [4]二分木、およびより一般的には次数が制限された木の描画は、描画スタイルに応じて線形またはほぼ線形の面積を持つ。[5] [6] [7] [8] [9]すべての外部平面グラフには、頂点数の 2 乗以下の面積を持つ直線の外部平面描画がある。 [10] [11]屈曲や交差が許される場合、外部平面グラフの描画はほぼ線形の面積を持つ。[12] [13]ただし、直列並列グラフを描画するには、エッジをポリラインとして描画できる場合でも、 nに超多対数係数を掛けたよりも大きな面積が必要である。[14]
指数関数的境界
これらの多項式境界とは対照的に、一部の描画スタイルでは面積が指数関数的に増大することがあり、これはこれらのスタイルが小さなグラフにのみ適している可能性があることを意味しています。一例は、平面有向非巡回グラフの上向き平面描画で、 n頂点の描画の面積は最悪の場合でも2nに比例することがあります。 [15]平面木でも、各頂点の周りに固定された巡回順序を維持し、頂点の周りに等間隔で配置する必要がある直線エッジで描画する場合は、指数関数的な面積が必要になる場合があります。 [16]
参考文献
- ^ ディ・バッティスタ、ジュゼッペ;イーデス、ピーター;タマシア、ロベルト; トリス、イオアニス G. (1998)、『グラフ描画：グラフの視覚化アルゴリズム』（第 1 版）、プレンティス ホール、pp. 14–15、ISBN 0133016153。
- ^ Dolev, Danny ; Leighton, Tom ; Trickey, Howard (1984)、「平面グラフの平面埋め込み」(PDF)、Advances in Computing Research、2 : 147–161
- ^ de Fraysseix, Hubert; Pach, János ; Pollack, Richard (1988)、「平面グラフのファリー埋め込みをサポートする小さなセット」、第20回ACMコンピューティング理論シンポジウム、pp. 426–433、doi : 10.1145/62212.62254、ISBN 0-89791-264-0、S2CID 15230919。
- ^ Schnyder, Walter (1990)、「グリッドへの平面グラフの埋め込み」、Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA)、pp. 138–148。
- ^ Crescenzi, P.; Di Battista, G.; Piperno, A. (1992)、「バイナリツリーの上向き描画のための最適領域アルゴリズムに関する注記」、計算幾何学理論と応用、2 (4): 187–200、doi :10.1016/0925-7721(92)90021-J、MR 1196545。
- ^ Garg, Ashim; Goodrich, Michael T. ; Tamassia, Roberto (1996)、「最適面積による平面上向きツリー描画」、International Journal of Computational Geometry & Applications、6 (3): 333–356、doi :10.1142/S0218195996000228、MR 1409650。
- ^ Chan, TM (2002)、「二分木を描くための近線形領域境界」、Algorithmica、34 (1): 1–13、doi :10.1007/s00453-002-0937-x、MR 1912924、S2CID 5122671。
- ^ Chan, Timothy M. ; Goodrich, Michael T. ; Kosaraju, S. Rao ; Tamassia, Roberto (2002)、「直線直交ツリー描画における面積とアスペクト比の最適化」、計算幾何学理論と応用、23 (2): 153–162、doi :10.1016/S0925-7721(01)00066-9、MR 1922928。
- ^ Garg, Ashim; Rusu, Adrian (2004)、「線形領域と任意のアスペクト比を持つバイナリツリーの直線描画」、Journal of Graph Algorithms and Applications、8 (2): 135–160、doi : 10.7155/jgaa.00086、MR 2164808。
- ^ Garg, Ashim; Rusu, Adrian (2007)、「外平面グラフの面積効率の良い平面直線描画」、Discrete Applied Mathematics、155 (9): 1116–1140、doi : 10.1016/j.dam.2005.12.008、MR 2321019。
- ^ ディ・バッティスタ、ジュゼッペ; Frati、Fabrizio (2009)、「Small area drawing of externalplanar charts」、Algorithmica、54 (1): 25–53、doi :10.1007/s00453-007-9117-3、MR 2496664、S2CID 2814656。
- ^ Biedl, Therese (2002)、「 O ( n log n ) の面積で外平面グラフを描画する」、グラフ描画:10th International Symposium、GD 2002、米国カリフォルニア州アーバイン、2002 年 8 月 26 ～ 28 日、改訂版論文、Lecture Notes in Computer Science、vol. 2528、Springer、pp. 54 ～ 65、doi : 10.1007/3-540-36151-0_6、MR 2063411。
- ^ Di Giacomo, Emilio; Didimo, Walter; Liotta, Giuseppe; Montecchiani, Fabrizio (2013)、「辺あたりの交差が少ないグラフ描画の面積要件」、計算幾何学理論と応用、46 (8): 909–916、doi : 10.1016/j.comgeo.2013.03.001、MR 3061453。
- ^ Frati, Fabrizio (2011)、「直列並列グラフの面積要件の下限の改善」、グラフ描画: 第 18 回国際シンポジウム、GD 2010、コンスタンツ、ドイツ、2010 年 9 月 21 ～ 24 日、改訂選択論文、Lecture Notes in Computer Science、vol. 6502、pp. 220 ～ 225、doi : 10.1007/978-3-642-18469-7_20、MR 2781267。
- ^ Di Battista, Giuseppe; Tamassia, Roberto; Tollis, Ioannis G. (1992)、「平面上向き描画の面積要件と対称表示」、Discrete and Computational Geometry、7 (4): 381–401、doi : 10.1007/BF02187850、MR 1148953。
- ^ Duncan, Christian A.; Eppstein, David ; Goodrich, Michael T .; Kobourov, Stephen G.; Nöllenburg, Martin (2013)、「完全な角度解像度と多項式面積によるツリーの描画」、Discrete and Computational Geometry、49 (2): 157–182、arXiv : 1009.0581、doi :10.1007/s00454-012-9472-y、MR 3017904、S2CID 5000871。