与えられたノードのピクセル位置をエッジルーティングするためのアルゴリズム？

Question

ノードと他のエッジとのエッジの重なりを最小限に抑えるグラフ内のさまざまなノードにエッジを生成するアルゴリズムは何ですか？

基本的に、キャンバスに（幅、高さ、xs、yの）ボックスの束があり、それらのいくつかの間にエッジを描きたいとします。さらに、エッジは、特定のポイント（つまり、左端の上から正確に5ピクセル）でボックス上のポイントに接続する必要があります。

これは他の人が以前考えていた最適化の問題だと思います。

Answer 1

グラフ交差数の計算と最小化に興味があるようです。それはNP困難な問題です。here'sこの問題はあまり古いものではなく、Helena's Master's thesisはグラフ交差数問題のアルゴリズム分析の包括的な始まりです。