Алгоритм планеризации графа

MerKish

Не подскажете, какие есть алгоритмы планеризации графов? В том смысле, что есть граф, а мы хотим расположить его вершины и рёбра на плоскости так, чтобы последние не пересекались (предполагаем, что граф планарный, т.е. без подграфов, гомеоморфных K5 и K3,3).
Лучше всего ссылки на какие-нибудь статьи про это дело.

soldatiki

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

Lokomotiv59

Нашел интересный диссер по теме:
http://www.nishizeki.ecei.tohoku.ac.jp/nszk/nishi/phd/saidur...
Там правда все больше про ортогональные, прямоугольные и прочие укладки повышенной красоты, но может по ссылкам что-то найдется.
PS. Если тут ничо нет, то запросами к гуглу типа "planar+graph+drawing" можно довольно много всего найти.

Lokomotiv59

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

toxin

Самого алгоритма нет, но идею понять можно: PQ tree.

liliya63

Я когда-то читал про "гамма алгоритм" или "алгоритм гамма", применяющийся для этого. Наверняка, его описание можно найти в интернете.

stealth

Существуют книжки, где описано несколько алгоритмов для плоской укладки планарных графов. Из того, что могу вспомнить на скорую руку:
http://www.logobook.ru/prod_show.php?object_uid=11146473
http://yafanat.ru/good/24968

roza200611

как найдешь или придумаешь - выложи сюда, плиз. тоже интересно!

toxin

Погугли по BoyerMyrvold2004.8.3.pdf - этот алгоритм по-видимому наиболее прост для понимания.
Оставить комментарий
Имя или ник:
Комментарий: