Constructing self-non-intersecting OE-chains in a plane Eulerian graph

The paper is devoted to a polynomial-time algorithm for constructing a self-non-intersecting ordered enclosing chain for a plane Eulerian graph. The proposed approach consists in splitting all the vertices of the original graph of degree higher than 4 and introducing fictive vertices and edges and, thus, reducing the considered earlier problem to the problem of finding an A-chain with ordered enclosing in a plane connected 4-regular graph. The presented reduction algorithm solves the problem in polynomial time. A test example of constructing a self-non-intersecting chain with ordered enclosing is considered. This problem arises during the technological preparation of the cutting process, when it is necessary to determine the path of the cutter when there are no self-intersections of the cutting path and the part cut off from the sheet does not require any cuts. The cutting plan may be presented as a planar graph which is the homeomorphic image of the cutting plan. The algorithm proposed in the article solves the problem of routing when cutting parts when such technological constraints are simultaneously imposed on the path of the cutter.