Алгоритм оптимальной отрисовки графа

Добрейшего времени суток, уважаемые!

Под термином "оптимальная" будем понимать, например min(X*((N*N)!)+sum(Li)), где X - количество пересечений ребер графа на рисунке, N - количество вершин графа, Li - длину i-того ребра (в чем угодно, сантиметрах, пикселях, не важно).

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

Какие есть мысли по сабжу? Может есть уже какие-то готовые решения?

PS. Поинмаю, формула "оптимальности" от балды. Хотелось просто показать, что наиболее важный критерий - уменьшение количества пересечений ребер.

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

Одна из самых известных библиотек:
http://www.graphviz.org/

Еще что-то тут:
http://alenacpp.blogspot.ru/2006/02/blog-post_10.html
https://en.wikipedia.org/wiki/Graph_drawing

Цитата Akina @ 28.12.15, 09:40

даже не сказано, направленный он или нет

Направленность значения не имеет. Речь идет о размещении вершин на плоскости. Пусть "знакоместо" вершины для направленного графа включает возможность прорисовки в нем "стрелки", если граф направленный".

Добавлено 28.12.15, 09:48
MBo, спасибо! И за материалы, и за оперативность! Буду разбираться, благо там и исходники в наличии.

Цитата MBo @ 28.12.15, 09:42

Еще что-то тут:

Точно!!! Де жа вю ...

Самое простое - разместить вершины на окружности.

Цитата foreach @ 31.12.15, 12:31

Самое простое - разместить вершины на окружности.

Но не всегда даёт нужный результат.
Полный граф с четырьмя вершинами является плоским, а размещая вершины на окружности, его без пересечения рёбер нарисовать нельзя.

Цитата amk @ 01.01.16, 08:35

Но не всегда даёт нужный результат.

Я бы даже так сказал: если планарный граф перерисовать, расположив его вершины на окружности, то с вероятностью 1, будут пересечения рёбер. (см. замечание ниже).

Цитата amk @ 01.01.16, 08:35

размещая вершины на окружности, его без пересечения рёбер нарисовать нельзя.

Подразумевая под рёбрами прямые отрезки.

Если произвольными кривыми рисовать, то вершины можно размещать как угодно - плоский граф можно будет нарисовать без пересечений.

Цитата amk @ 01.01.16, 09:55

плоский граф можно будет нарисовать без пересечений.

Даже если, к примеру, 10 вершин соединены все-ко-всем?

Цитата JoeUser @ 14.01.16, 16:20

Даже если, к примеру, 10 вершин соединены все-ко-всем?

Он не планарен будет!

Добавлено 14.01.16, 16:26
П.С. полный граф на K вершинах становится непланарным уже при K>4.

Цитата Славян @ 14.01.16, 16:24

П.С. полный граф на K вершинах становится непланарным уже при K>4.

Вот поэтому и я засумневался А откуда инфа про K>4?

Цитата JoeUser @ 14.01.16, 16:38

Вот поэтому и я засумневался

В чём?

Цитата JoeUser @ 14.01.16, 16:38

А откуда инфа про K>4?

Широко известное утверждение.

Добавлено 14.01.16, 16:42

Цитата вики

Графы с K₁ по K₄ являются планарными. Полные графы с большим количеством вершин не являются планарными, так как содержат подграф K₅ и, следовательно, не удовлетворяют критерию Понтрягина-Куратовского.

Цитата Славян @ 14.01.16, 16:41

В чём?

В сообщении №9 (о непересечении).

Цитата Славян @ 14.01.16, 16:41

Широко известное утверждение.

И ты умудрился его "обрезать" ... а оно в вики звучит так:

Цитата

Необходимое условие — если граф непланарный, то он должен содержать больше 4 вершин, степень которых больше 3, или больше 5 вершин степени больше 2.