Построение самонепересекающихся $OE$-маршрутов в плоском эйлеровом графе

В статье предложен полиномиальный алгоритм построения самонепересекающегося маршрута с упорядоченным охватыванием в плоском эйлеровом графе. Предложенный подход состоит в расщеплении всех вершин исходного графа степени выше 4 и введении фиктивных вершин и ребер, сводя, таким образом, исходную задачу к решенной ранее автором задаче построения $A$-цепи с упорядоченным охватыванием в плоском связном 4-регулярном графе. Приведенный алгоритм сведения решает поставленную задачу за полиномиальное время. Рассмотрен тестовый пример построения самонепересекающейся цепи с упорядоченным охватыванием. Данная задача возникает при технологической подготовке процесса раскроя, когда требуется определить маршрут движения режущего инструмента, при котором отсутствуют самопересечения траектории резки и отрезанная от листа часть не требует разрезаний. Раскройный план представлен в виде плоского графа, являющегося его гомеоморфным образом. Предложенный в статье алгоритм решает проблему маршрутизации при вырезании деталей, когда на маршрут движения режущего инструмента одновременно наложены такие технологические ограничения.