Minimierung der Anzahl von Kreuzungen in einem zweiteiligen Graphen
Das folgende Algorithmusproblem ist mir aufgefallen, als ich ein Diagramm für etwas Nichtverwandtes gezeichnet habe:
Wir haben eine Ebenenzeichnung eines zweiteiligen Graphen, wobei die disjunkten Gruppen wie gezeigt in Spalten angeordnet sind. Wie können wir die Knoten innerhalb jeder Spalte so umordnen, dass die Anzahl der Kantenübergänge minimiert wird? Ich weiß, dass dieses Problem für allgemeine Graphen NP-schwer ist ( link ), aber gibt es einen Trick wenn man bedenkt, dass der Graph zweigeteilt ist?
Wie geht es weiter, wenn es eine dritte Spalte w gibt, die nur Kanten zu v hat? Oder weiter?
2 Antworten
Das Papier Auf der einseitigen Kreuzung Minimierung in einem zweiteiligen Graphen mit großen Graden von Hiroshi Nagamochi erwähnt, dass das Originalpapier auf der Überfahrtsnummer von Garey und Johnson hat auch bewiesen, dass die Anzahl der Kantenübergänge minimiert wird ist NP-schwer für bipartite Graphen. In der Tat ist es immer noch NP-schwer Selbst wenn Ihnen die optimale Reihenfolge für eine Spalte gesagt wird:
Bei einem zweiteiligen Diagramm besteht eine zweischichtige Zeichnung aus Platzierungsknoten in der ersten Knotenmenge V auf einer geraden Linie L1 und Platzieren von Knoten in der zweiter Knotensatz W auf einer parallelen Linie L2. Das Problem der Minimierung die Anzahl der Übergänge zwischen Bögen in einer 2-Schichten-Zeichnung war zuerst eingeführt von Harary und Schwenk. Die einseitige Kreuzungsminimierung Problem fragt, um eine Reihenfolge der Knoten in V auf L1 so zu finden dass die Anzahl der Bogenkreuzungen minimiert wird (während die die Knoten in W auf L2 sind gegeben und fixiert). Anwendungen des Problems kann in VLSI-Layouts und hierarchischen Zeichnungen gefunden werden.
Die zweiseitigen und einseitigen Probleme sind jedoch NP-schwer von Garey und Johnson sowie von Eades und Wormald.
Peter de Rivaz wies darauf hin, dass es NP-Hard ist, aber wenn es Ihnen mit einer Annäherung gut geht, können Sie mit der folgenden Lösung gehen.
Mein anfänglicher Gedanke war, einen Algorithmus mit Kraftaufwand für das Layout von Graphen zu verwenden, aber es kann etwas mühsam sein, ihn zu implementieren. Aber hey, da ist dieses wunderbare Programm graphviz.org , das die ganze Arbeit für dich erledigen kann.
Nach der Installation bereiten Sie einfach eine Datei mit Ihrem Graphen vor:
%Vor% Ausführen: dot -Tpng yourgraph -o yourgraph.png
und so etwas für free erhalten: -):
Tags und Links algorithm graph bipartite planar-graph