Loading article…
グラフ描画において、グラフのRAC 描画は、頂点が点として表され、辺が直線セグメントまたはポリラインとして表され、最大 2 つの辺が任意の点で交差し、2 つの辺が交差する場合は互いに直角に交差する描画です。この描画スタイルの名前の「RAC」は、「直角交差」の略です。
直角交差スタイルと、このスタイルに対する「RAC描画」という名前は、Didimo、Eades、Liotta (2009) [1]によって考案されました。これは、以前のユーザー研究で、角度の大きい交差は浅い交差よりも描画の可読性に悪影響が少ないことが示されたことに触発されたものです。[2]平面グラフの場合でも、グラフの描画で直角交差をいくつか許可すると、面積や角度解像度などの描画品質の指標が大幅に向上します。[3]
例
完全グラフ K 5には直線の辺を持つRAC描画がありますが、K 6 には直線の辺がありません。6頂点のRAC描画には最大14の辺しかありませんが、K 6には15の辺があり、RAC描画には多すぎます。[1]
完全二部グラフ K a , b は、 min( a , b ) ≤ 2 またはa + b ≤ 7 のいずれかのときに限り、直線のエッジを持つ RAC 描画を持つ。 min( a , b ) ≤ 2 の場合、グラフは平面グラフであり、（ファリの定理により）すべての平面グラフは交差のない直線描画を持つ。このような描画は自動的に RAC 描画になる。残る 2 つのケースはグラフK 3,3とK 3,4である。 K 3,4の描画が示されている。K 3,3は、このグラフから頂点を 1 つ削除することで作成できる。次の 2 つの大きなグラフK 4,4とK 3,5のどちらもRAC 描画を持たない。[4]
エッジと曲げ
n頂点グラフ ( n ≥ 4) に直線のエッジを持つ RAC 描画がある場合、そのグラフが持つエッジの数は最大で 4 n − 10 です 。これは厳密です。RAC 描画可能なグラフには、ちょうど 4 n − 10 のエッジを持つものがあります。[1]折れ線エッジを持つ描画の場合、グラフのエッジ数の上限は、エッジごとに許可される曲げの数によって決まります。エッジごとに 1 つまたは 2 つの曲げを持つ RAC 描画を持つグラフには、O( n ) 個のエッジがあります。より具体的には、曲げが 1 つの場合、最大で 5.5 n 個のエッジがあります[5]。曲げが 2 つの場合、最大で 74.2 n 個のエッジがあります。[6]すべてのグラフには、エッジごとに 3 つの曲げを持つ RAC 描画があります。[1]
1平面性との関係
グラフが1 平面グラフであるとは、1 辺につき最大 1 つの交差を持つ描画がある場合です。直感的には、この制限により、この交差を直角にすることが容易になり、 直線 RAC 描画の辺の数の4 n − 10 の境界は、 1 平面グラフ の辺の数の4 n − 8 の境界、および 直線 1 平面グラフの辺の数の4 n − 9 の境界に近いです。4 n − 10 辺を持つすべての RAC 描画は 1 平面グラフです。[7] [8]さらに、すべての外側 1 平面グラフ (つまり、すべての頂点が描画の外側の面にある、1 辺につき 1 つの交差を持つグラフ) には RAC 描画があります。[9]ただし、 RAC 描画を持たない4 n − 10 辺を持つ 1 平面グラフも存在します。 [7]
計算の複雑さ
与えられたグラフが直線のエッジを持つRAC描画を持つかどうかを判断することはNP困難である[10]。たとえ入力グラフが1平面で、出力RAC描画も1平面でなければならないとしても。[11]より具体的には、RAC描画は実数の存在理論に対して完全である。[12] RAC描画問題は、有向非巡回グラフの上向き描画に対してNP困難のままである。[13]しかし、外側が1平面のグラフの特殊なケースでは、RAC描画は線形時間で構築できる。[14]
参考文献
- ^ abcd Didimo, Walter; Eades, Peter ; Liotta, Giuseppe (2009)、「直角交差によるグラフの描画」、アルゴリズムとデータ構造: 第 11 回国際シンポジウム、WADS 2009、バンフ、カナダ、2009 年 8 月 21 ～ 23 日。議事録、コンピュータ サイエンスの講義ノート、vol. 5664、pp. 206 ～ 217、doi :10.1007/978-3-642-03367-4_19、ISBN 978-3-642-03366-7。
- ^ Huang, Weidong; Hong, Seok-Hee ; Eades, Peter (2008)、「交差角度の影響」、IEEE Pacific Visualization Symposium (PacificVIS '08)、pp. 41–46、doi :10.1109/PACIFICVIS.2008.4475457、ISBN 978-1-4244-1966-1。
- ^ van Kreveld, Marc (2011)、「平面グラフの RAC 描画と平面描画の品質比」、グラフ描画: 第 18 回国際シンポジウム、GD 2010、コンスタンツ、ドイツ、2010 年 9 月 21 ～ 24 日、改訂選択論文、コンピュータ サイエンスの講義ノート、vol. 6502、pp. 371 ～ 376、doi : 10.1007/978-3-642-18469-7_34、ISBN 978-3-642-18468-0。
- ^ ディディモ、ウォルター;イードス、ピーター; リオッタ、ジュゼッペ (2010)、「完全な二部RACグラフの特徴付け」、情報処理レター、110 (16): 687–691、doi :10.1016/j.ipl.2010.05.023、MR 2676805。
- ^ Angelini, Patrizio; Bekos, Michael; Förster, Henry; Kaufmann, Michael (2018) 「辺ごとに1つの曲げがあるグラフのRAC描画について」arXiv : 1808.10470
- ^ ありくし、かりん;フレック、ラドスラフ。ケシェグ、バラズ。モリッチ、フィリップ。 Tóth、Csaba D. (2012)、「直角交差描画を許可するグラフ」、Computational Geometry Theory & Applications、45 (4): 169–177、arXiv : 1001.3117、doi : 10.1016/j.comgeo.2011.11.008、MR 2876688。
- ^ ab Eades, Peter ; Liotta, Giuseppe (2013)、「直角交差グラフと 1 平面性」、離散応用数学、161 (7–8): 961–969、doi : 10.1016/j.dam.2012.11.019、MR 3030582。
- ^ アッカーマン、エヤル (2014)、「1平面グラフに関する注記」、離散応用数学、175 :104–108、doi : 10.1016/j.dam.2014.05.025、MR 3223912。
- ^ Dehkordi, Hooman Reisi; Eades, Peter (2012)、「すべての外側 1 平面グラフには直角交差図がある」、International Journal of Computational Geometry & Applications、22 (6): 543–557、doi :10.1142/S021819591250015X、MR 3042921。
- ^ Argyriou, Evmorfia N.; Bekos, Michael A.; Symvonis, Antonios (2011)、「直線 RAC 描画問題は NP 困難」、SOFSEM 2011: 37th Conference on Current Trends in Theory and Practice of Computer Science、Nový Smokovec、スロバキア、2011 年 1 月 22 ～ 28 日、議事録、Lecture Notes in Computer Science、vol. 6543、pp. 74 ～ 85、arXiv : 1009.5227、Bibcode :2011LNCS.6543...74A、doi :10.1007/978-3-642-18381-2_6、ISBN 978-3-642-18380-5
- ^ Bekos, Michael A.; Didimo, Walter; Liotta, Giuseppe; Mehrabi, Saeed; Montecchiani, Fabrizio (2017)、「1平面グラフのRAC描画について」、理論計算機科学、689 :48–57、arXiv : 1608.08418、doi :10.1016/j.tcs.2017.05.039
- ^ Schaefer, Marcus (2021)、「RAC 描画可能性は-complete」、第 29 回グラフ描画およびネットワーク可視化国際シンポジウム (GD 2021) の議事録、arXiv : 2107.11663
- ^ Angelini, Patrizio; Cittadini, Luca; Di Battista, Giuseppe; Didimo, Walter; Frati, Fabrizio; Kaufmann, Michael; Symvonis, Antonios (2010)、「直角交差描画によって開かれる視点について」、Graph Drawing : 17th International Symposium, GD 2009、シカゴ、イリノイ州、米国、2009 年 9 月 22 ～ 25 日、改訂版論文、Lecture Notes in Computer Science、vol. 5849、pp. 21 ～ 32、doi : 10.1007/978-3-642-11805-0_5、ISBN 978-3-642-11804-3。
- ^ クリストファー・アウアー;バックマイヤー、クリスチャン。ブランデンブルク、フランツ J.ハナウアー、キャスリン。グライスナー、アンドレアス。ニューワース、ダニエル。 Reislhuber、Josef (2013)、「線形時間における外部 1 平面グラフの認識」、グラフ描画 LNCS、コンピューター サイエンスの講義ノート、8284 : 107–118、doi :10.1007/978-3-319-03841-4、ISBN 978-3-319-03840-7
