Планарная укладкка графа

[Berje]

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

[незваный гость]

mathworld утверждает, что все алгоритмы проверки планарности сложные. Википедия не вполне согласна (посмотрите также статью "on cutting edge", на которую ссылаются в конце).

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