Распознавание планарности и построение плоской укладки

Найти в графе какой-нибудь простой цикл и уложить его.

Пока есть не уложенные ребра, повторять

найти грани уложенного подграфа, сегменты и допустимые грани для каждого сегмента;

если для некоторого сегмента нет допустимых граней, то граф не планарен, стоп;

если есть сегменты, имеющие только одну допустимую грань, то пусть – такой сегмент, иначе выбрать любой сегмент ;

в сегменте найти путь , соединяющий две контактные вершины этого сегмента и не содержащий других контактных вершин;

уложить путь в одну из допустимых граней для сегмента .

В применении к рассмотренному примеру в качестве должен быть выбран сегмент , а в качестве пути можно взять, например, путь (3, 1, 7, 8). Он должен быть уложен в грань , после чего она разобьется на две новых грани.