绘制一般平面图的组合嵌入。

Question

我有一个通用平面图的组合嵌入（包括顶点、边、围绕顶点的边的循环顺序和外部面），需要将其绘制出来。

顶点必须是无量纲的，绘图必须遵守定义的围绕顶点的边的循环顺序（以及外部面），即使输入图形不是3连通或最大平面图也是如此。

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

- user2267134

Answer 1

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

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

关于使用哪个算法，我建议联系开发者Szabolcs Horvát。

- licheng