Пусть построена некоторая укладка подграфа Н графа G сегментом S относительно Н будем называть подграф графа G одного из след. видов
а. ребро е = uv из Eg: е не принадлежит Еh и v принадлежит Еh;
б. связную компоненту графа G - Н, дополненную всеми ребрами G инцидентными вершинам взятой компоненты
вершину v сегмента S назовем контактной, если v принадлежит Vh
допустимой гранью для S относительно Н наз-ся грань Г графа Н, содержащая все контактные вершины сегмента S
Алгоритм:
1. выбрать простой цикл С графа G и уложить его на плоскости Н = С;
2. найти грани G и сегменты относительно Н, если мн-во сегментов пусто, то перейти к шагу 7;
3. для каждого сегмента S определить мн-во Гs. Если сущ-т сегмент S для которого Гs = пусто, то G не планарен и конец алгоритма, а иначе идти дальше
4. если 
сегмент S для которого имеется единств. допустимая грань Г, то перейти к шагу 6, а иначе к шагу 5
5. для некоторого сегмента S : Гs больше 1, выбрать произвольную допустимую грань Г.
6. поместить пр-ую α-цепь из S в грань Г. Заменить Н на Н U(объединение) αC и перейти к шагу 1
7. построена укладка графа G на плоскость
свойства планарных графов
1.максимальное число некратных ребер плоского графа 3n-6;
2.если число некратных ребер графа <= n+2, то граф заведомо плоский.
3.если число некратных ребер графа > 3n - 6, то граф не плоский;
