Special Type Routing Problems in Plane Graphs

Tatiana Makarovskikh and Anatoly Panyukov
Additional contact information
Tatiana Makarovskikh: Department of System Programming, South Ural State University, 454080 Chelyabinsk, Russia
Anatoly Panyukov: Department of System Programming, South Ural State University, 454080 Chelyabinsk, Russia

Mathematics, 2022, vol. 10, issue 5, 1-22

Abstract: We considered routing problems for plane graphs to solve control problems of cutting machines in the industry. According to the cutting plan, we form its homeomorphic image in the form of a plane graph G . We determine the appropriate type of route for the given graph: O E -route represents an ordered sequence of chains satisfying the requirement that the part of the route that is not passed does not intersect the interior of its passed part, A O E -chain represents O E -chain consecutive edges which are incident to vertex v and they are neighbours in the cyclic order O ± ( v ) , N O E -route represents the non-intersecting O E -route, P P O E -route represents the Pierce Point N O E -route with allowable pierce points that are start points of O E -chains forming this route. We analyse the solvability of the listed routing problems in graph G . We developed the polynomial algorithms for obtaining listed routes with the minimum number of covering paths and the minimum length of transitions between the ending of the current path and the beginning of the next path. The solutions proposed in the article can improve the quality of technological preparation of cutting processes in CAD/CAM systems.

Keywords: routing; plane graph; polynomial algorithm (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/5/795/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/5/795/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:5:p:795-:d:762518

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().