[dimarik]

Подскажите, пожалуйста, алгоритм создания максимально плоского графа G(V).

Добавлено через 25 часов 30 минут
Максимально плоский граф (на плоскости, граф, в который невозможно добавить ребро без пересечения других ребер) является триангулированным; все его грани образованы тремя вершинами. В том числе и внешняя грань. Построение графа можно начать с единственной внутренней грани, добавляя следующую вершину в неё и разбивая последнюю на три новых грани. Кстати, "Паучки" и им подобное развлекалово являются разряженным плоским графом. Вроде кто-то задавал вопрос как создать граф для этой игры.