Плоская укладка графа, проверка на планарность.

[Fret]

Задан граф, положение в пространстве неизвестно, нужно нарисовать его с минимальным количеством пересечений рёбер.
Наверное тут проверка на планарность не требуется. Если в подграфе есть пересечения, то и рисовать с ними.

Посоветуйте алгоритмы или книжки на эту тему.

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

[Maslov]

Погуглите "визуализация графов".
Кое-что есть в Касьянов, Евстигнеев. Графы в программировании: обработка, визуализация и применение.