Verbindungen zwischen Knoten optimieren -> Wenig überschneidungen

[scooter010]

Moin!

Ich habe leider keine Ahnung wonach ich googeln soll...

Ich habe eine Menge an Knoten. Jeder Knoten kann mit einer beliebigen Anzahl anderer Knoten verbunden sein.
Anzahl der Verbindungen pro Knoten < Anzahl der Knoten.
Der Knoten hat nur die eigne ID und die IDs der mit ihm verbundenen Knoten als Eigenschaft (wie Binärbaum, nur nicht Binär).

Die Knoten sollen nun in einer Ebene angeordnet werden.
Das Kriterium zur Anordnung soll sein, dass sich die Verbindungen zwischen den Knoten möglichst selten überschneiden.

Wie löse ich das (also die Anordnung der Knoten, nicht die grafische Darstellung)? Jemand einen Tipp?

 

[benneq]

Deine Knotensammlung nennt sich "Graph" (Ein Baum ist ein spezieller Graph)

Graphen ohne sich überschneidende Kanten sind "planar".

 

[scooter010]

Ah, der Wikieintrag hilft schon mal weiter. Optimieren nach Kantenkreuzungen