Прямолинейное плоское вложение структуры графа

Question

Вот моя проблема: у меня есть структура графа (с прямыми ребрами), которая, как я знаю, является плоской (то есть существует вложение графа, где ребра не пересекаются).Мне нужен алгоритм, который возьмет мой график и произведет прямолинейное встраивание его.Алгоритм не должен быть слишком эффективным (алгоритм O (N ^ 2) подойдет).Есть идеи / предложения?

Answer 1

Прочитайте документ ...

У меня был этот проект для моего курса по Алгоритмам, чтобы встроить график, который мы использовали в формате SVG ... Как только вы определились с алгоритмом, формат SVG легко генерируется ...

Answer 2

вы можете захотеть в графвизе (http://www.graphviz.org/). Это позволит нарисовать его во многих различных форматах и ​​довольно простое определение ввода. Для создания графиков можно использовать несколько алгоритмов.

в противном случае, вычеркните алгоритм планарности Бойера-Мирволда и отсортированный код c из википедии: http://jgaa.info/accepted/2004/BoyerMyrvold2004.8.3/planarity.zip