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

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

Под термином "оптимальная" будем понимать, например 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.

Цитата JoeUser @ 14.01.16, 17:05

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

Там всё чётко и правильно написано. Всё же непонятно в чём сомнение. Сформулируйте сами или мы с вами в чём-то запутались.

Добавлено 14.01.16, 17:12

Цитата JoeUser @ 14.01.16, 17:10

И ты умудрился его "обрезать"

Нет, я написал всё абсолютно чётко. Приведите мою цитату, кою считаете обрезаной, там и разберём подробнее.

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

Цитата JoeUser @ 14.01.16, 17:14

Славян, ты издеваешься?

Нет.

Цитата JoeUser @ 14.01.16, 17:14

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

Утверждение amk - истинно.

Цитата JoeUser @ 14.01.16, 17:14

В втором случае - я специально выделил красным цветом "обрезанное".

Всё же приведите мою фразу, кою считаете неточной, ибо все они истинны и не обрезаны!

Добавлено 14.01.16, 17:22
Вот моё полное утверждение:

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

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

Оно истинно без каких-либо добавок!

Цитата Славян @ 14.01.16, 17:19

Утверждение amk - истинно.

А как же "полный граф на K>4"?
Ну и вдогоночку ... Если утверждаешь, что истинно, нарисуй полный планарный граф с 7-ю вершинами. Линии могут быть кривыми. У меня чет не получилось.

Цитата Славян @ 14.01.16, 17:19

Оно истинно без каких-либо добавок!

Да, термин "полный", я упустил. Оно истинно без каких-либо добавок!

Цитата JoeUser @ 14.01.16, 17:32

Цитата Славян @ 14.01.16, 17:19

Утверждение amk - истинно.

А как же "полный граф на K>4"?

Эх... Вот, что он утверждал: "если граф плоский и можно рисовать рёбра кривыми, то этот плоский граф можно будет нарисовать без пересечений, даже если вершины располагать не в каких-то особых местах, а где угодно".

Цитата Славян @ 14.01.16, 17:43

Эх... Вот, что он утверждал: "если граф плоский и можно рисовать рёбра кривыми, то этот плоский граф можно будет нарисовать без пересечений, даже если вершины располагать не в каких-то особых местах, а где угодно".

Цитата JoeUser @ 14.01.16, 17:32

нарисуй полный планарный граф с 7-ю вершинами

Осилишь кривыми?

Цитата JoeUser @ 14.01.16, 18:01

Осилишь кривыми?

Опять за рыбу деньги. Написано же:

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

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

Т.е. не существует 'полных планарных графов с 7-ю вершинами'.

Цитата Славян @ 14.01.16, 18:07

Т.е. не существует 'полных планарных графов с 7-ю вершинами'.

Цитата Славян @ 14.01.16, 17:19

Утверждение amk - истинно.

Так а что же утверждал amk? Ну то, что ты написал - истинным?

Читаем:

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

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

Ограничений нет, Значит любой. В том числе и ... планарный граф с 7-ю вершинами.

Цитата JoeUser @ 14.01.16, 18:21

Ограничений нет, Значит любой.

Ограничение есть - читайте внимательно - 'плоский граф'!!!

Цитата JoeUser @ 14.01.16, 18:21

В том числе и ... планарный граф с 7-ю вершинами.

Вы, наверное, хотели написать "полный планарный с 7-ю ве..."?, так вот полных плоских=планарных с 7-ю ве. не существует.

Ты меня уморил. Попытаюсь последний раз:

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

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

Разбираем утверждение:

1) используем кривые
2) вершины располагаем где угодно на плоскости (плоский граф)
3) граф любой, как полный так и не полный, т.к. написано только "плоский граф"

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

Цитата JoeUser @ 14.01.16, 18:50

Ты меня уморил. Попытаюсь последний раз:

Грустно. Ну если у меня не получится, то оставлю ваши непонимания самому автору - amk, он сможет проянить, уверен!
Поехали:

Цитата JoeUser @ 14.01.16, 18:50

Ты утверждаешь, что это истинно.

Да.

Цитата JoeUser @ 14.01.16, 18:50

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

Итак, согласно п.3 можно нарисовать и полный и не полный (это вы верно подметили). Однако условие планарности накладывает ограничение на многообразие таких полных, коих не много остаётся в этом классе, а именно только с 1..4 вершинами туда входят. Когда же вершин более 4-х, то граф перестаёт быть плоским, а значит происходит нарушение п.3 и мы вываливаемся из области действия трёх условий. Уф... как-то так.

Цитата Славян @ 14.01.16, 19:00

Итак, согласно п.3 можно нарисовать и полный и не полный (это вы верно подметили). Однако условие планарности накладывает ограничение на многообразие таких полных, коих не много остаётся в этом классе, а именно только с 1..4 вершинами туда входят. Когда же вершин более 4-х, то граф перестаёт быть плоским, а значит происходит нарушение п.3 и мы вываливаемся из области действия трёх условий. Уф... как-то так.

Просьба была не выкручиваться, приплетая измышления и домыслы, и дополнительные ограничения, которых нет в утверждении фактически. А нарисовать. Вобщем. Сколько волка не корми, а утро вечера мудренее. Забили.

Цитата JoeUser @ 14.01.16, 18:50

2) вершины располагаем где угодно на плоскости (плоский граф)

Нет термина "плоский граф", но достаточно очевидно, что в данном случае под плоским понимался планарный.

JoeUser, вместо того, чтобы выяснить, что подразумевалось под словами "плоский граф", ты затеял тут непонятно что. Как заметил OpenGL, такого термина не существует, но слово-то написано, значит какие-то ограничения под ним подразумеваются.
Я не сверяю каждое написанное слово со справочниками. Я не математик, занимающийся изучением графов. Я даже по работе с графами как таковыми сталкиваюсь не часто. А если они попадаются, мне как-то не удаётся на эту тему с кем-то пообщаться (я не уверен даже, что у меня на работе кто-то помнит, что такое планарный граф). У меня память пока неплохая, но обычно я запоминаю не конкретные слова а только их смысл, а слово "планарный" означает что-то вроде "размещаемый на плоскости". Плюс слово планарный имеет кучу однокоренных с совсем другими значениями. Вот и ошибся.
Планарный граф это граф, который можно разместить на плоскости без пересечения рёбер. И утверждение моё было всего лишь о том, что перемещение вершин не вызывает появления пересечений. Всегда можно найти непрерывное отображение плоскости, переводящее одно расположение вершин в другое. Соответственно оно преобразует и рёбра, но пересечений при этом не возникнет.

Цитата OpenGL @ 15.01.16, 13:36

Нет термина "плоский граф", но достаточно очевидно, что в данном случае под плоским понимался планарный.

Да.

Цитата amk @ 16.01.16, 06:18

Вот и ошибся.

Дружище! Ошибаются все! Мне важно было выявить, что ошибка была, и где была. В деталях. И как можно было бы тоже самое сделать/выразить без ошибки. Ну и вершиной всего - решение вопросов первого сообщения. Все норм, не парься! И спасибо за участие!