曲げの最小化

グラフのエッジをポリライン（折れ線で接続された線分のシーケンス）で表すグラフ描画スタイルでは、エッジあたりの折れ線の数（曲線の複雑さと呼ばれることもある）^[1]または描画内の折れ線の総数を最小化することが望ましい。^[2]折れ線最小化は、これらの量を最小化する描画を見つけるアルゴリズムの問題である。 ^[3]^[4]

あらゆる曲がりをなくす

曲がりの最小化の典型的な例はファリーの定理であり、これはすべての平面グラフが曲がりなしで、つまりすべての辺が直線分として描かれることができることを述べている。 ^[5]

グラフの辺が曲がらず軸が揃っている描画は、直線描画と呼ばれることもあり、交差が全て直角となるRAC描画を構成する一つの方法である。 ^{[6]しかし、}平面グラフに平面直線描画があるかどうかを判断することはNP完全であり、 ^[7]任意のグラフに交差を許す直線描画があるかどうかを判断することもNP完全である。^[6]

曲げの最小化

Tamassia (1987) は、頂点が整数格子に配置され、辺が軸に沿ったポリラインとして描かれる平面グラフの直交描画のベンド最小化は、問題を最小コストのネットワークフローの問題に変換することで多項式時間で実行できることを示した。^[8]^{[9]しかし、グラフの平面埋め込みが変更される可能性がある場合、ベンド最小化は NP 完全となり、代わりに}整数計画法などの手法で解決する必要があるが、これは高速な実行時間と正確な答えの両方を保証するものではない。^[10]

エッジあたりの曲がりが少ない

多くのグラフ描画スタイルでは曲げが許可されていますが、制限があります。これらの描画の曲線の複雑さ（辺あたりの曲げの最大数）は、ある固定定数によって制限されています。この定数を大きくすると、描画の面積など、他の側面を改善できます。^[1]あるいは、場合によっては、曲げが許可されている場合にのみ描画スタイルが可能な場合があります。たとえば、すべてのグラフに曲げのないRAC 描画（すべての交差が直角の描画）や曲線の複雑さが 2 の描画があるわけではありませんが、曲線の複雑さが 3 の描画はすべてのグラフにあります。^[11]

参考文献

^ ab Di Giacomo, Emilio; Didimo, Walter; Liotta, Giuseppe; Meijer, Henk (2011)、「非平面グラフ描画の面積、曲線の複雑さ、交差解像度」、Theory of Computing Systems、49 (3): 565–575、doi :10.1007/s00224-010-9275-6、MR 2822838。
^ ディ・バッティスタ、ジュゼッペ;イーデス、ピーター;タマシア、ロベルト; トリス、イオアニス G. (1998)、『グラフ描画：グラフの視覚化アルゴリズム』（第 1 版）、プレンティスホール、pp. 15–16、ISBN 978-0133016154。
^ ディ・バティスタら。 (1998)、p. 145.
^ パーチェス、ヘレン(1997)、「人間の理解に最も大きな影響を与える美学は何か?」、グラフ描画: 第 5 回国際シンポジウム、GD '97 ローマ、イタリア、1997 年 9 月 18 ～ 20 日、議事録、コンピュータサイエンスの講義ノート、第 1353 巻、pp. 248 ～ 261、doi : 10.1007/3-540-63938-1_67、ISBN 978-3-540-63938-1。
^ ディ・バティスタら。 (1998)、p. 140.
^ ab Eades, Peter ; Hong, Seok-Hee ; Poon, Sheung-Hung (2010)、「グラフの直線描画について」、Graph Drawing: 17th International Symposium、GD 2009、シカゴ、イリノイ州、米国、2009 年 9 月 22 ～ 25 日、改訂版論文、Lecture Notes in Computer Science、vol. 5849、Springer、pp. 232 ～ 243、doi : 10.1007/978-3-642-11805-0_23、ISBN 978-3-642-11804-3、MR 2680455。
^ Garg, Ashim; Tamassia, Roberto (2001)、「上向きおよび直線平面性テストの計算複雑性について」、SIAM Journal on Computing、31 (2): 601–625、doi :10.1137/S0097539794277123、MR 1861292。
^ Tamassia, Roberto (1987)、「最小の曲げ数でグリッドにグラフを埋め込むことについて」、SIAM Journal on Computing、16 (3): 421–444、doi :10.1137/0216030、MR 0889400。
^ コルネルセン、サビーネ、カレンバウアー、アンドレアス（2012）、「加速ベンド最小化」、グラフアルゴリズムとアプリケーションジャーナル、16（3）：635–650、doi：10.7155 / jgaa.00265、MR 2983428。
^ Mutzel, Petra ; Weiskircher, René (2002)、「整数計画法を用いた直交描画の曲げ最小化」、Computing and Combinatorics: 8th Annual International Conference、COCOON 2002、シンガポール、2002 年 8 月 15 ～ 17 日、議事録、Lecture Notes in Computer Science、vol. 2387、pp. 484 ～ 493、CiteSeerX 10.1.1.138.1513、doi :10.1007/3-540-45655-4_52、ISBN 978-3-540-43996-7。
^ 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、ISBN 978-3-642-03366-7。

[ddlm-1] Di Giacomo, Emilio; Didimo, Walter; Liotta, Giuseppe; Meijer, Henk (2011)、「非平面グラフ描画の面積、曲線の複雑さ、交差解像度」、Theory of Computing Systems、49 (3): 565–575、doi :10.1007/s00224-010-9275-6、MR 2822838。

[gda-2] ディ・バッティスタ、ジュゼッペ;イーデス、ピーター;タマシア、ロベルト; トリス、イオアニス G. (1998)、『グラフ描画：グラフの視覚化アルゴリズム』（第 1 版）、プレンティスホール、pp. 15–16、ISBN 978-0133016154。

[3] ディ・バティスタら。 (1998)、p. 145.

[4] パーチェス、ヘレン(1997)、「人間の理解に最も大きな影響を与える美学は何か?」、グラフ描画: 第 5 回国際シンポジウム、GD '97 ローマ、イタリア、1997 年 9 月 18 ～ 20 日、議事録、コンピュータサイエンスの講義ノート、第 1353 巻、pp. 248 ～ 261、doi : 10.1007/3-540-63938-1_67、ISBN 978-3-540-63938-1。

[5] ディ・バティスタら。 (1998)、p. 140.

[ehp-6] Eades, Peter ; Hong, Seok-Hee ; Poon, Sheung-Hung (2010)、「グラフの直線描画について」、Graph Drawing: 17th International Symposium、GD 2009、シカゴ、イリノイ州、米国、2009 年 9 月 22 ～ 25 日、改訂版論文、Lecture Notes in Computer Science、vol. 5849、Springer、pp. 232 ～ 243、doi : 10.1007/978-3-642-11805-0_23、ISBN 978-3-642-11804-3、MR 2680455。

[7] Garg, Ashim; Tamassia, Roberto (2001)、「上向きおよび直線平面性テストの計算複雑性について」、SIAM Journal on Computing、31 (2): 601–625、doi :10.1137/S0097539794277123、MR 1861292。

[8] Tamassia, Roberto (1987)、「最小の曲げ数でグリッドにグラフを埋め込むことについて」、SIAM Journal on Computing、16 (3): 421–444、doi :10.1137/0216030、MR 0889400。

[9] コルネルセン、サビーネ、カレンバウアー、アンドレアス（2012）、「加速ベンド最小化」、グラフアルゴリズムとアプリケーションジャーナル、16（3）：635–650、doi：10.7155 / jgaa.00265、MR 2983428。

[10] Mutzel, Petra ; Weiskircher, René (2002)、「整数計画法を用いた直交描画の曲げ最小化」、Computing and Combinatorics: 8th Annual International Conference、COCOON 2002、シンガポール、2002 年 8 月 15 ～ 17 日、議事録、Lecture Notes in Computer Science、vol. 2387、pp. 484 ～ 493、CiteSeerX 10.1.1.138.1513、doi :10.1007/3-540-45655-4_52、ISBN 978-3-540-43996-7。

[11] 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、ISBN 978-3-642-03366-7。