Wie kann die Anzahl der Kreuzungskanten in einem Diagramm verringert werden?

9

Ich arbeite an einem Diagrammeditor. Diagramme zeigen 2D-Formen ( Knoten ) an, die mit Verbindern ( Kanten ) verbunden sind.

Ich möchte eine Operation hinzufügen, die sie bei einer Auswahl von Knoten "entwirrt" : Sie positioniert sie neu, um die Anzahl der sich kreuzenden Kanten nach Möglichkeit zu verringern (und es ist in Ordnung, wenn die Kanten mit Biegepunkten gezeichnet werden müssen). .

Ich möchte also einen Graph-Algorithmus, der bei einer ( topologischen ) Graph-Einbettung und einer Teilmenge seiner Knoten die Einbettung (seine Topologie ) nur auf diesen Knoten modifiziert , um die Anzahl der sich kreuzenden Kanten zu minimieren.

Nach dem Lesen über Apex-Diagramme und dem Durchsuchen von Cabello und Mohar (2013) ist dieses Problem vermutlich NP-schwer. Ich bin also mit einem parametrisierten Algorithmus (z. B. der Anzahl der Kreuzungskanten) zufrieden, der für jeden gegebenen Parameterwert eine bekannte polynomielle Zeitkomplexität aufweist. Dies scheint machbar, aber ich finde es nicht einfach, selbst einen solchen Algorithmus zu entwickeln.

Fragen:

  • Wo suche ich nach einem solchen Algorithmus?
  • Existiert es?
  • In vorhandener Software?
  • Gibt es bedeutende praktische Erfahrungen mit einer solchen Operation? (Was theoretisch gut aussieht, ist in der Praxis möglicherweise nicht so gut oder umgekehrt.)

(Ich bin mir nicht sicher, wo ich diese Frage am besten stellen soll: hier auf StackOverflow oder MathOverflow?)

Reinierpost
quelle
1
Ich würde annehmen, dass die Frage besser für StackOverflow geeignet ist, aber ich habe festgestellt, dass ähnliche Fragen dort unbefriedigende Antworten haben. Ich werde eine Antwort geben, die Ihnen am theoretischen Ende helfen sollte, aber es ist möglicherweise am besten, wenn Ihre Frage dorthin migriert wird.
mdxn
Hier wird sehr gründlich
Dschoni
Vielen Dank! Nicht nur das, es ist auch eine sehr gut lesbare Darstellung des Problems und eine Übersicht über einige bekannte Ansätze.
Reinierpost

Antworten:

8

Die Berechnung der absoluten minimalen Kreuzungszahl ist, wie Sie beobachtet haben, . Das Zeichnen der Diagramme sollte mindestens so schwierig sein.NP-hard

Das in der Frage aufgeworfene Problem ist tatsächlich schwieriger und komplizierter als das oben genannte. Sie betrachten Diagrammknoten einer bestimmten Größe und Form und begrenzen gleichzeitig die Größe (Fläche) des Ergebnisses. Darüber hinaus ist ein noch nicht festgelegter Begriff der Ästhetik erwünscht. Offensichtlich wollen wir dafür eine Heuristik, die im allgemeinen Fall nicht das absolute Minimum verwendet. Die Anzahl der in einer solchen Anwendung angetroffenen Knoten ist im Durchschnitt wahrscheinlich nicht groß. Das Zeichnen der Version mit minimaler Kantenüberschneidung des Diagramms kann für kleine Größen möglich sein.

Ressourcen:
Möglicherweise interessieren Sie sich für die folgenden Ressourcen, insbesondere für die erste:

Es gibt auch viele andere Ressourcen. Diese sollen Ihnen den Einstieg erleichtern.

Zusätzliche Gedanken und Beobachtungen:

Hier ist eine Idee, um die Probleme bezüglich der Form und Größe von Knoten zu umgehen. Erweitern Sie angesichts des Diagramms (unendlich kleine Knoten) jeden Knoten, während Sie Kanten "schieben" oder aus dem Weg biegen (z. B. mithilfe von Splines, während Sie die Nähe einschränken). Sie müssen dies mit anderen Kanten und Knoten tun, die dem im Weg stehen und eine Kettenreaktion auslösen können. Untersuchen Sie, wie ein Gleichgewicht effizient berechnet werden kann (z. B. molekulare Strukturen). Wenn Sie die Form eines Knotens nicht auf die gewünschte Größe bringen können, skalieren Sie das gesamte Diagramm.

Ein Benutzer kann die Ergebnisse eines zufälligen Algorithmus genießen. Sie könnten Ihre Funktion mehrmals verwenden, bis sie etwas bekommen, das ihnen gefällt. Vermeiden Sie in diesem Fall redundante Berechnungen (Sie müssen keine Kreuzungsnummer erneut berechnen).

mdxn
quelle
Ich habe meine Frage speziell topologisch ergänzt , um die Diskussion über Ästhetik zu vermeiden. Es ist wichtig, aber ich denke nicht, dass sie das Grundproblem stark beeinflussen - ich denke, sie können in einem separaten Schritt behandelt werden, nachdem die Topologie der Knoten angepasst wurde (dh welche Knoten von welchen anderen Knoten umgeben sind).
Reinierpost
Ich habe Graphviz vor über 15 Jahren zum ersten Mal verwendet. Ich benutze es ungefähr einmal pro Woche für alle Arten von Grafiken. Ich bin nicht sehr beeindruckt von den Ergebnissen und ich verstehe, dass es schwierig ist, es viel besser zu machen.
Reinierpost
Ich besuche oft graphviz.org und habe einige der Artikel gelesen, auf die sie sich beziehen. Aber ich habe noch keine Antwort auf diese spezielle Frage gefunden, und es steht nicht in meiner Stellenbeschreibung, sich mit der Literatur vertraut zu machen. Deshalb frage ich es hier.
Reinierpost
Vielen Dank für die Referenzen - ich stelle fest, dass dies immer noch aktuelle Forschung ist .
Reinierpost
Das erste, was ich versuchen werde, ist ein trivialer (und daher nicht unbedingt nützlicher) Algorithmus, der grob auf Frau Shabbeers Idee basiert. Danke noch einmal.
Reinierpost