2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Планарная укладкка графа
Сообщение01.04.2006, 11:15 
Доброго времени суток,
Задача стандартная, по матрице смежности графа сказать планарный или не планарный и если планарный то нарисовать его планарную укладку. Подскажите наиболее подходящий алгоритм по соотношению эффективность и простота алгоритма. Требуется написать как можно за ментшее время(1-2 недели) поэтому супер сложных алгоритмов не надо;)И подскаажите где почитать про это что посмотреть.
Заранее спасибо,

 
 
 
 
Сообщение01.04.2006, 21:43 
Аватара пользователя
:evil:
mathworld утверждает, что все алгоритмы проверки планарности сложные. Википедия не вполне согласна (посмотрите также статью "on cutting edge", на которую ссылаются в конце).

Что же касается рисования, то самый существует много алгоритмов (и, как я к своему изумлению выяснил -- много книг). Попробуйте google ("рисование графов", "graph drawing"). Основной алгоритм, с которым я сталкивался -- spring (основан на перевычислении графа с пружинками в качестве ребер), встречается barycenter (каждая точка распологается в центре тяжести соседей). Мне понравился обзор Браденбурга, но он не без грехов, и, к тому же устарел (2002 г.).

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group