Für den Zweck dieser Stelle von einem ebenen Graphen oder eine ebene Karte, werde ich ein abstraktes Diagramm bedeuten, die in der Ebene gezogen werden können (oder äquivalent auf der Kugel), zusammen mit der kreisförmigen Ordnung der Kanten an jeder Ecke entsprechend einer bestimmten Zeichnung. Diese zusätzliche Information bestimmt die Einbettung auf der Kugel (bis zu beweglichen Ecken und Kanten, so dass sie niemals andere Ecken/Kanten schneiden). I tun wollen Schleifen und mehrere Kanten zulassen.Implementationen von planaren Graphen/Karten (mit Einbettungen)
Angenommen, wir haben ein Diagramm wie folgt erstellt. Zeichnen Sie zwei Scheitelpunkte (A und B) in der Ebene, zusammen mit zwei Kanten, die diese beiden verbinden. Die beiden Kanten bilden zusammen eine einfache geschlossene Kurve \ gamma. Fügen Sie nun zwei weitere Scheitelpunkte, A 'und B', hinzu und verbinden Sie A und A 'mit einer Kante und B und B' ebenfalls.
Dieser abstrakte Graph wird zwei ungleiche Einbettungen haben, je nachdem, ob die Ecken A 'und B' durch die Kurve \ Gamma getrennt sind oder nicht.
Meine Frage ist: Gibt es ein Python-Paket, das eine solche ebene Graphen implementiert?
Ich interessiere mich für ein Paket, das eine Zeichnung eines ebenen Graphen erstellen kann (natürlich unter Berücksichtigung der Einbettung), sowie einige Standardoperationen ausführt (z. B. die Anzahl der Flächen angeben, eine Doppellinie bilden usw.)
Wenn ein solches Paket in Python nicht existiert, würde ich mich auch für Implementierungen in anderen Sprachen interessieren.
Natürlich gibt es verschiedene Pakete, die das Zeichnen von Graphen und graphentheoretischen Algorithmen implementieren. Allerdings habe ich an keiner dieser Möglichkeiten die Möglichkeit erkannt, mit Graphen zu arbeiten, die bereits mit einer Einbettung versehen sind. Eine Referenz würde sehr geschätzt werden.