外平面嵌入算法

Question

有谁知道可以生成图的外平面嵌入的算法吗？我正在寻找类似于 NetworkX 中的 check_planarity 的东西，如果图是平面的，它会返回平面嵌入，每个节点都知道其入射边的顺时针顺序。反例就没有必要了。

即使只是向我指出相关文献以便我能够自己实现这一点也会非常有帮助。或者任何关于我如何解决这个问题的想法也会对我有很大帮助！

维基百科的一些定义： 在图论中，

平面图是可以嵌入平面中的图，即可以在平面上绘制其边仅在端点相交的方式。换句话说，它可以以没有边相互交叉的方式绘制。这样的绘图称为平面图，或图的平面嵌入。

外平面图是一种无向图，可以在平面上绘制而无需交叉，使得所有顶点都属于绘图的无界面。也就是说，没有顶点完全被边包围。

这是我正在进行的网络路由实验的一部分。我尝试过在这种情况下搜索相关文献，但我相信我可能需要在图论或更数学的东西中进行搜索才能找到更多相关信息。

Answer 1

对于任何可能遇到同样问题的人，我是这样解决的：

#1) 将外平面图扩充为双连通外平面图：

def make_biconnected(graph):
    # Find cut vertices
    cut_vertices = list(nx.articulation_points(graph))

    for v in cut_vertices:
        neighbors = list(graph.neighbors(v))

        # Partition neighbors into blocks based on biconnected components
        subgraph = nx.Graph(graph)
        subgraph.remove_node(v)
        blocks = []
        for component in nx.connected_components(subgraph):
            block_neighbors = [n for n in neighbors if n in component]
            if block_neighbors:
                blocks.append(block_neighbors)

        # Add edges between blocks to make the graph biconnected
        for j in range(len(blocks) - 1):
            u = blocks[j][-1]
            w = blocks[j + 1][0]
            if not graph.has_edge(u, w):
                graph.add_edge(u, w)

                # If the edge breaks outerplanarity, revert and try other combinations
                if not is_outerplanar(graph):
                    graph.remove_edge(u, w)
                    for u_alt in blocks[j]:
                        for w_alt in blocks[j + 1]:
                            if not graph.has_edge(u_alt, w_alt):
                                graph.add_edge(u_alt, w_alt)
                                if is_outerplanar(graph):
                                    break
                                graph.remove_edge(u_alt, w_alt)

    return graph

#2）找到最大的简单循环（这应该是哈密顿循环或外面）并使用节点排序来创建圆形布局

def generate_pos(graph):
    cycles = list(nx.simple_cycles(graph))
    maxLength = max( len(l) for l in cycles )
    path = list(l for l in cycles if len(l) == maxLength)
    pos = nx.circular_layout(path[0])
    return pos

#3) 使用#2 中的位置和原始外平面图的边，使用一些数学方法按 ccw 顺序对每个节点的邻居列表进行排序，并将边添加到嵌入中。

def convert_to_outerplanar_embedding(graph, pos):
    # Step 1: Create a PlanarEmbedding object
    planar_embedding = nx.PlanarEmbedding()

    # Step 2: Assign the cyclic order of edges around each node based on positions
    for node in graph.nodes:
        neighbors = list(graph.neighbors(node))
        
        # Sort neighbors counterclockwise based on angle relative to the node's position
        neighbors.sort(key=lambda n: math.atan2(pos[n][1] - pos[node][1], pos[n][0] - pos[node][0]))

        # Step 3. Add edges in sorted order to the embedding
        planar_embedding.add_half_edge(node, neighbors[0])
        for i in range(1, len(neighbors)):
            u = neighbors[i-1]
            v = neighbors[i] 
            planar_embedding.add_half_edge(node, v, ccw = u)
    return planar_embedding

结果可以使用 nx.draw_planar 绘制，并且应该看起来像外平面图。我还没有对其进行广泛的测试，但到目前为止它对于我的用例来说是有效的。