2014-02-04
557
Найти в графе какой-нибудь простой цикл и уложить его.
Пока есть не уложенные ребра, повторять
найти грани уложенного подграфа, сегменты и допустимые грани для каждого сегмента;
если для некоторого сегмента нет допустимых граней, то граф не планарен, стоп;
если есть сегменты, имеющие только одну допустимую грань, то пусть 
– такой сегмент, иначе выбрать любой сегмент ;
в сегменте найти путь 
, соединяющий две контактные вершины этого сегмента и не содержащий других контактных вершин;
уложить путь в одну из допустимых граней для сегмента .
В применении к рассмотренному примеру в качестве должен быть выбран сегмент 
, а в качестве пути можно взять, например, путь (3, 1, 7, 8). Он должен быть уложен в грань 
, после чего она разобьется на две новых грани.
