Jak zmniejszyć liczbę skrzyżowanych krawędzi na schemacie?

Pracuję nad edytorem diagramów. Diagramy przedstawiają kształty 2D ( węzły ) połączone ze złączami ( krawędziami ).

Chciałbym dodać operację, która, biorąc pod uwagę wybór węzłów, „rozplątuje” je: zmienia ich położenie, jeśli to możliwe, aby zmniejszyć liczbę przecinających się krawędzi (i jest w porządku, jeśli krawędzie będą musiały być rysowane za pomocą punktów zgięcia) .

Chcę więc algorytmu graficznego, który, biorąc pod uwagę ( topologiczny ) osadzanie wykresu i podzbiór jego węzłów, modyfikuje osadzanie (jego topologię ) tylko na tych węzłach, aby zminimalizować liczbę przecinających się krawędzi.

Czytając o wykresach wierzchołków i przeglądając Cabello i Mohara (2013) , przypuszczam, że ten problem jest trudny do rozwiązania. Będę więc zadowolony ze sparametryzowanego algorytmu (np. Liczby przecinających się krawędzi), który ma znaną wielomianową złożoność czasową dla dowolnej wartości parametru. Wydaje się to wykonalne, ale nie jest mi łatwo wymyślić taki algorytm.

Pytania:

• Gdzie szukać takiego algorytmu?
• Czy to istnieje?
• W istniejącym oprogramowaniu?
• Czy jest jakieś istotne praktyczne doświadczenie z taką operacją? (To, co w teorii wygląda dobrze, może nie być tak dobre w praktyce lub odwrotnie.)

(Nie jestem pewien, gdzie najlepiej zadać to pytanie: tutaj, na StackOverflow lub MathOverflow?)

Obliczenie absolutnej minimalnej liczby przekroczeń jest, jak zauważyłeś, $\text{NP-hard}$. Proces rysowania wykresów powinien być co najmniej tak trudny.

Problem postawiony w pytaniu jest w rzeczywistości trudniejszy i bardziej zaangażowany niż powyższe. Rozważasz węzły wykresu o określonym rozmiarze i kształcie, jednocześnie ograniczając rozmiar (obszar) wyniku. Ponadto pożądane jest jeszcze nieokreślone pojęcie estetyki. Oczywiście chcemy do tego heurystyki, która nie wykorzystuje absolutnego minimum w ogólnym przypadku. Liczba węzłów napotkanych w takiej aplikacji prawdopodobnie nie jest duża w przeciętnym przypadku. Rysowanie wersji wykresu z minimalnym przekraczaniem krawędzi może być wykonalne w przypadku małych rozmiarów.

Zasoby:
Mogą Cię zainteresować następujące zasoby, szczególnie pierwsze:

• Dokumentacja funkcji pakietu Graphviz przedstawia algorytm, który generuje ładnie wyglądające ukierunkowane wykresy: http://www.graphviz.org/Documentation/TSE93.pdf
  Posiada wiele innych funkcji, które mogą się okazać przydatne. Kod źródłowy znajduje się na ich stronie internetowej pod EPL. Zawiera także stronę poświęconą teorii związanej z wizualizacją grafów.
• Aby uzyskać algorytm o stałych parametrach , sprawdź artykuł Martina Grohe:
  Obliczanie liczb przekraczania w czasie kwadratowym
• Przemówienie technologiczne wygłoszone przez Aminę Shabbeer w RPI: Zachowanie relacji bliskości i minimalizacja przekroczeń krawędzi w osadzeniach
  grafów
• Przykład skutecznego algorytmu probabilistycznego można znaleźć w tym artykule Julii Chuzhoy:
  Algorytm dla problemu przekroczenia wykresu

Istnieje również wiele innych zasobów. To powinno ci pomóc zacząć.

Dodatkowe przemyślenia i obserwacje:

Oto pomysł na obejście problemów dotyczących kształtu i wielkości węzłów. Biorąc pod uwagę wykres (nieskończenie małe węzły), rozwiń każdy węzeł, jednocześnie „wypychając” lub zginając krawędzie (np. Używając splajnów, jednocześnie egzekwując ograniczenie odległości). Musisz to zrobić z innymi krawędziami i węzłami, które mu przeszkadzają, co może rozpocząć reakcję łańcuchową. Przyjrzyj się, jak można skutecznie obliczyć równowagę (np. Struktury molekularne). Jeśli nie możesz uzyskać kształtu węzła do żądanego rozmiaru, przeskaluj cały diagram.

Użytkownik może cieszyć się wynikami losowego algorytmu. Mogą używać tej funkcji wiele razy, dopóki nie uzyskają czegoś, co im się podoba. W takim przypadku unikaj nadmiarowych obliczeń (nie musisz ponownie obliczać numeru przecięcia).