Bagaimana cara mengurangi jumlah garis silang dalam diagram?

Saya sedang mengerjakan editor diagram. Diagram menampilkan bentuk 2D ( node ) yang terhubung dengan konektor ( tepi ).

Saya ingin menambahkan operasi yang, diberi pilihan node, "pisahkan" mereka: itu memposisikan mereka untuk mengurangi jumlah tepi yang bersilangan, jika mungkin (dan tidak apa-apa jika ujung-ujungnya harus digambar dengan titik tikungan) .

Jadi saya ingin algoritma grafik yang, diberi embedding ( topologi ) grafik dan subset dari node-nya, memodifikasi embedding ( topologi -nya ) hanya pada node-node itu untuk meminimalkan jumlah crossing edge.

Dari membaca tentang grafik puncak dan menjelajah Cabello dan Mohar (2013) , saya kira masalah ini NP-hard. Jadi saya akan senang dengan algoritma parametrized (misalnya pada jumlah tepi persimpangan) yang memiliki kompleksitas waktu, polinomial, diketahui untuk setiap nilai parameter yang diberikan. Ini tampaknya layak, tetapi saya tidak merasa mudah untuk membuat algoritma sendiri.

Pertanyaan:

• Di mana saya mencari algoritma seperti itu?
• Apakah itu ada
• Dalam perangkat lunak yang ada?
• Adakah pengalaman praktis yang signifikan dengan operasi semacam itu? (Apa yang tampak baik secara teori mungkin tidak begitu baik dalam praktiknya, atau sebaliknya.)

(Saya tidak yakin di mana sebaiknya menanyakan pertanyaan ini: di sini, di StackOverflow, atau MathOverflow?)

$\text{NP-hard}$

Masalah yang diajukan dalam pertanyaan sebenarnya lebih sulit dan lebih terlibat daripada yang di atas. Anda sedang mempertimbangkan node grafik dari ukuran dan bentuk tertentu sementara juga membatasi ukuran (area) dari hasil. Selain itu, gagasan estetika yang belum ditentukan diinginkan. Jelas kami ingin heuristik untuk ini, yang tidak menggunakan minimum absolut dalam kasus umum. Jumlah node yang ditemui dalam aplikasi seperti itu kemungkinan tidak besar dalam kasus rata-rata. Menggambar versi persimpangan tepi minimal grafik mungkin layak untuk ukuran kecil.

Sumber daya:
Anda mungkin tertarik pada sumber daya berikut, terutama yang pertama:

• Dokumentasi untuk fitur paket Graphviz menyajikan algoritma yang menghasilkan grafik terarah yang terlihat bagus: http://www.graphviz.org/Documentation/TSE93.pdf
  Ini memiliki beberapa fitur lain yang mungkin berguna. Kode sumber terletak di situs web mereka di bawah EPL. Ini juga termasuk halaman yang didedikasikan untuk teori di balik visualisasi grafik.
• Untuk algoritma parameter-tetap periksa makalah oleh Martin Grohe:
  Computing Crossing Numbers in Quadratic Time
• Pembicaraan teknis yang diberikan oleh Amina Shabbeer di RPI:
  Menjaga Hubungan Kedekatan dan Meminimalkan Edge-crossing dalam Graph Embeddings
• Contoh algoritma probabilistik yang efisien dapat ditemukan dalam makalah ini oleh Julia Chuzhoy:
  Algoritma untuk Graph Crossing Number Problem

Ada banyak sumber daya lain juga. Ini akan membantu Anda memulai.

Pikiran & Pengamatan Tambahan:

Berikut adalah ide untuk menyiasati masalah tentang bentuk dan ukuran node. Mengingat grafik (node ​​sangat kecil), perluas setiap node sambil "mendorong" atau menekuk ujungnya (mis. Menggunakan splines sambil memaksakan batas pada kedekatan). Anda perlu melakukan ini dengan tepi dan simpul lain yang menghalangi, yang dapat memulai reaksi berantai. Lihatlah bagaimana keseimbangan dapat dihitung secara efisien (mis. Struktur molekul). Jika Anda tidak bisa mendapatkan bentuk simpul dengan ukuran yang diinginkan, maka skala seluruh diagram.

Seorang pengguna dapat menikmati hasil dari algoritma acak. Mereka dapat menggunakan fitur Anda beberapa kali hingga mereka mendapatkan sesuatu yang mereka sukai. Hindari perhitungan yang berlebihan dalam hal ini (tidak perlu menghitung nomor persimpangan lagi).