Нарисуйте комбинаторное вложение общего плоского графа

Question

Нарисуйте комбинаторное вложение общего плоского графа

У меня есть комбинаторное вложение общего плоского графа (вершины, ребра, циклическое упорядочение ребер вокруг вершин и внешней грани), и мне нужно его нарисовать.

Вершины должны быть многомерными, и чертеж должен соответствовать определенному циклическому упорядочению ребер вокруг вершин (и с внешней гранью), даже если входной граф не является 3-связным или максимально плоским.

Было бы лучше, если бы алгоритм рисования уже был реализован (возможно, в библиотеке Java), но бумаги с объяснением алгоритма все еще достаточно.

5

java graph planar-graph

Источник

user2267134 26 июн '13 в 16:17

1 ответ

Другие вопросы по тегам java graph planar-graph

user14872220 12 сен '23 в 12:17 2023-09-12 12:17 · Answer 1 · 2023-09-12 12:17

Я рекомендую 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"]
 ]

По поводу того, какой алгоритм использовать, я рекомендую обратиться к разработчику Сабольчу Хорвату.