Konstruktion planarer Graph

[DerNewbie]

Hi zusammen, bastle gerade an einem "Grapheneditor" der aus gegebenen Kanten und Knoten
Beispiel für Eingabe einen planaren Graphen konstruiert. Wie die Grafik könnte eine Eingabe des Benutzers aussehen.
Dabei sind k1...k7 eingegebene Knoten und das andere Kanten, die der Benutzer eingeben hat.
Das ergebnis soll zum Beispiel wie folgt aussehen:
Ergebnis. Das als Ergebnis eine einfacher geschlossener Pfad rauskommt ist nicht umbedingt wichtig, nur alle Kanten sollen, falls möglich Kreuzungsfrei sein.
Meine Überlegung ist, das ganze über einen Minimalen Spannbaum zu berechnen. Aber vielleicht
gibt es noch andere, bessere Ansätze.

Viele Grüße Lars