绘制通用平面图的组合嵌入

Question

我有通用平面图的组合嵌入（顶点、边、顶点周围边的循环排序和外部面），我需要绘制它。

顶点必须是无维的，并且绘图必须符合顶点周围（以及外部面）边定义的循环顺序，即使输入图不是 3 连通图或最大平面图。

如果绘图算法已经实现（也许在 Java 库中），那就更好了，但是一篇带有算法解释的论文仍然足够了。

Answer 1

我推荐IGraph/M，它是一个用于复杂网络和图论研究的 Mathematica 包。

\n

    Needs["IGraphM`"]\n    s = <|1 -> {11, 12, 13}, 2 -> {3, 20, 8}, 3 -> {2, 4, 42}, \n       4 -> {3, 5, 28}, 5 -> {4, 6, 34}, 6 -> {5, 7, 46}, \n       7 -> {6, 10, 30}, 8 -> {2, 22, 9}, 9 -> {8, 23, 10}, \n       10 -> {9, 25, 7}, 11 -> {1, 15, 14}, 12 -> {1, 27, 29}, \n       13 -> {1, 32, 31}, 14 -> {11, 16, 22}, 15 -> {11, 19, 16}, \n       16 -> {15, 17, 14}, 17 -> {16, 18, 21}, 18 -> {17, 19, 24}, \n       19 -> {18, 15, 25}, 20 -> {2, 41, 26}, 21 -> {17, 23, 22}, \n       22 -> {21, 8, 14}, 23 -> {21, 24, 9}, 24 -> {23, 18, 25}, \n       25 -> {24, 19, 10}, 26 -> {20, 39, 27}, 27 -> {26, 35, 12}, \n       28 -> {4, 29, 40}, 29 -> {28, 12, 35}, 30 -> {7, 31, 45}, \n       31 -> {30, 13, 36}, 32 -> {13, 33, 36}, 33 -> {32, 34, 43}, \n       34 -> {33, 5, 44}, 35 -> {29, 27, 37}, 36 -> {32, 38, 31}, \n       37 -> {35, 39, 40}, 38 -> {36, 43, 45}, 39 -> {37, 26, 41}, \n       40 -> {37, 42, 28}, 41 -> {39, 20, 42}, 42 -> {41, 3, 40}, \n       43 -> {38, 33, 44}, 44 -> {43, 34, 46}, 45 -> {38, 46, 30}, \n       46 -> {45, 44, 6}|>;(*combinatorial embedding*)\n      g = IGAdjacencyGraph[s] (*generate the graph)\n Graph[g, VertexCoordinates -> IGEmbeddingToCoordinates[s], \n VertexLabels -> Placed[Automatic, Center], VertexSize -> 0.5, \n VertexLabelStyle -> 6, ImageSize -> Large, \n VertexStyle -> ColorData["Legacy", "LemonChiffon"], \n EdgeStyle -> Darker@ColorData["Legacy", "IndianRed"]\n ]\n

\n

\n

至于使用哪种算法，我建议联系开发者 Szabolcs Horv\xc3\xa1t。

\n