Визуализация графа с вершинами на окружности

Может кто-нибудь поскажет какие-нибудь алогоритмы для визуализации графа на окружности?
Конкретно задача стоит так: сделать граф из n вершин размещенных на вершинах правильного многоульника и k ребер, не пересекающиъся с друг другом.

Зарание спасибо....

Прости непонил суть вопроса?

тебе надо розместить граф а круг?

Чем не подходит вичислять координати по кругу за счет угла?

a = Pi / Count
x[i] = xc + r * cos(a)
y[i] = yc + r * sin(a)

где (xc,yc) - координати круга... r - радиус ... a - угл поворота

Mishamp, рёбра графа не должны пересекаться.

Предположим у меня есть граф, мне нужно узнать смогу я разместить его вершины на углах правильного многоугольника или нет

Добавлено 04.03.11, 11:43
сорри, забыл уточнить, нужно чтобы связи не пересекались

Цитата OpenGL @ 04.03.11, 11:45

будет полезна любая помощь в этом направлении

http://forum.sources.ru/index.php?showtopic=224475&hl=

Цитата OpenGL @ 04.03.11, 12:07

http://forum.sources.ru/index.php?showtopic=224475&hl=

читал, но так и не понял к чему они там пришли

Там albom описал алгоритм. Если непонятно, вот алгоритм попроще:

• Пока граф не пуст:
  
  • Выбираем вершину со степенью меньше трех. Если такой вершины нет, граф уложить нельзя.
  • Удаляем эту вершину из графа и помещаем ее в стек. Если степень вершины была 2, то соединяем ребром те вершины, с которыми соединялась удаленная.
• Теперь по очереди достаем вершины из стека и пытаемся вставить куда-либо в окружность так, чтобы ребра не пересекались. Если не получается - вложить нельзя.

Цитата OpenGL @ 04.03.11, 12:23

Там albom описал алгоритм. Если непонятно, вот алгоритм попроще:

• Пока граф не пуст:
  
  • Выбираем вершину со степенью меньше трех. Если такой вершины нет, граф уложить нельзя.
  • Удаляем эту вершину из графа и помещаем ее в стек. Если степень вершины была 2, то соединяем ребром те вершины, с которыми соединялась удаленная.
• Теперь по очереди достаем вершины из стека и пытаемся вставить куда-либо в окружность так, чтобы ребра не пересекались. Если не получается - вложить нельзя.

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

тоисть тебе надо зделать проверку планарнии ли граф?

Планарнии ето тот катории можно разместити в плоскасти так чтоби ребра не пересикались


тогда ето всего лиш Теорема Понтрягина-Куратовского
Граф планарен тогда и только тогда, когда не содержит подграфов, гомеоморфных

http://ru.wikipedia.org/wiki/%D0%9F%D0%BB%D0%B0%D0%BD%D0%B0%D1%80%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84

Добавлено 04.03.11, 13:11
*планарный

Цитата Mishamp @ 04.03.11, 13:10

тоисть тебе надо зделать проверку планарнии ли граф?

Планарнии ето тот катории можно разместити в плоскасти так чтоби ребра не пересикались


тогда ето всего лиш Теорема Понтрягина-Куратовского
Граф планарен тогда и только тогда, когда не содержит подграфов, гомеоморфных

http://ru.wikipedia.org/wiki/%D0%9F%D0%BB%D0%B0%D0%BD%D0%B0%D1%80%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84

Добавлено 04.03.11, 13:11
*планарный

Планарный граф — граф, который может быть изображен на плоскости без пересечения ребер.

я думаю, не кажый такой граф можно будет визуализировать в виде правильного n-угольника собранного из его вершин

Не совсем так. Для того, чтобы граф был вложим в окружность, необходимо и достаточно чтобы он не содержал подграфов, гомеоморфных полному K4 и полному двудольному К 3 2.

Цитата OpenGL @ 04.03.11, 13:17

Не совсем так. Для того, чтобы граф был вложим в окружность, необходимо и достаточно чтобы он не содержал подграфов, гомеоморфных полному K4 и полному двудольному К 3 2.

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

цитата с другого форума


Цитата (Sergeyev)
Цитата (Adopt)
Планарный граф

Возник вопрос по графам:
Каким образом можно построить планарный граф по заранее известному количеству вершин, ребер?

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




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

Mishamp, разумеется, если граф укладывается в окружность, то он укладывается и в проскость, т.е. планарен. Обратное неверно - например, граф "квадрат с диагоналями" (К4) укладывается в плоскость, но не в окружность.