Учитывая, что все графики не являются плоскими (что вы знаете), возможно, было бы лучше использовать подход «следующий лучший», чем подход «всегда дает лучший ответ».
Я говорю этопотому что у моего соседа по комнате в аспирантуре была та же проблема, что и у тебя.Он пытался преобразовать график в плоскую форму, и все алгоритмы, гарантирующие минимальное пересечение ребер, были слишком медленными.Что он в итоге делал, что просто реализовывал рандомизированный алгоритм.По сути, выкладывайте график, затем перемещайте узлы, у которых есть ребра с множеством пересечений, и в конечном итоге вы справитесь с наихудшими скоплениями ребер.
Преимущества были: вы можете вырезать его после определенного количествавремя, так что если вы ограничены во времени, это всегда занимает определенное количество времени, если вы получаете дерьмовый график, вы можете просто запустить его снова (по уже выложенному графику), чтобы получить что-то лучше, и это относительно легкокод вверх.
Недостатком является то, что вы не всегда получаете глобальные минимумы в пересечениях, и если график застревает в областях с пересечением высоких скоростей, его алгоритм иногда отбрасывает узел на расстоянии, чтобы попытаться решитьэто, что иногда вызывает очень странно выглядящие графики.