python - 平面图/ map 的实现(带嵌入)

Question

在这篇文章中，平面图或平面图是指可以在平面(或等价物)中绘制的抽象图在球体上)，以及根据特定此类绘图在每个顶点处的边的圆形顺序。这个额外的信息决定了球体上的嵌入(直到移动顶点和边，使得它们永远不会与任何其他顶点/边相交)。我确实想要允许循环和多边。

例如，假设我们已经构建了一个图，如下所示。在平面上绘制两个顶点(A 和 B)，以及连接这两个顶点的两条边。两条边一起形成一条简单的闭合曲线\gamma。现在再添加两个顶点，A' 和 B'，并用边连接 A 和 A'，还有 B 和 B'。

根据顶点 A' 和 B' 是否被曲线\gamma 分开，这个抽象图将有两个不等价的嵌入。

---

我的问题是:是否有实现这种平面图的Python包？

我对可以创建平面图(当然是关于嵌入)以及执行一些标准操作(例如给出面数、形成对偶图等)的包很感兴趣

如果 Python 中不存在这样的包，我也会对其他语言的实现感兴趣。

---

当然有各种实现图形绘制和图论算法的包。但是，我没有注意到在这些中的任何一个中使用已经带有嵌入的图形的可能性。非常感谢您提供引用。

编辑。让我进一步详细说明。同一个图在球体中的两个嵌入是等价的，如果它们通过球体与其自身的同胚相关。如上所述，一般来说，平面图的嵌入不是唯一的，所以我要问的是不与测试图的平面度并绘制其中的一些嵌入相同。

有几种组合方式可以对嵌入进行编码，直到达到这种等价性。可能最简单的是记录每个顶点的边循环顺序(“旋转系统”)，但还有很多其他的。参见 the article on graph embeddings on Wikipedia供讨论和引用。

人们可能希望对这样的组合嵌入执行一些明显的操作，例如找到图的面，找到边/顶点相邻的面，在面中插入顶点，分割边，绘制嵌入图等。

是否有一个或多个这些数据结构的实现，表示 Python 中可用的组合图嵌入？ (我注意到图嵌入在一般表面上是有意义的，尽管我主要对球体的情况感兴趣。)

Answer 1

我刚刚注意到 networkx 确实包含一个用于我描述的目的的类，即 PlanarEmbedding。参见 https://networkx.github.io/documentation/latest/reference/algorithms/planarity.html

(我不确定这个是我问的时候介绍过的，还是我当时漏掉的。)

该类附带的方法看起来确实很基础，它只实现了一种可能的平面嵌入数据结构。我会进一步调查；如果有人知道其他实现，将不胜感激。