Geodesic
The algorithms for constructing of cutter optimal path
Journal of computational and engineering mathematics, Tome 1 (2014) no. 2, pp. 52-61.

Voir la notice de l'article provenant de la source Math-Net.Ru

This paper considers methods of automatic cutter path choice for laser equipment. Graphs are often used as mathematical models for different control problems or automated design. Particularly, for automated system of cutting process preparation the mathematical model of a cutting plan should be a topological plane graph. Nowadays a branch of graph theory dealing with constructing some paths and trails with different restrictions is rapidly developing. This research considers the following cutting problem formulated in the terms of graph theory. We need define a shortest cutter trajectory so that part cut out a sheet does not require further cuttings. If one considers the cutter trajectory to be a trail of a plane graph, the requirement of eliminating the necessity of cutting of a piece separated from the sheet can be formalized as the condition that internal faces of any initial part of the given trail does not intersect the graph edges. The polynomial algorithms presented in the paper allow to solve the routing problem either for connected or disconnected plane graph.
Keywords: Plane graph, Effective algorithm, Cutting process, Ordered enclosing, Path. 
@article{JCEM_2014_1_2_a5,
     author = {T. A. Makarovskikh},
     title = {The algorithms for constructing of cutter optimal path},
     journal = {Journal of computational and engineering mathematics},
     pages = {52--61},
     publisher = {mathdoc},
     volume = {1},
     number = {2},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JCEM_2014_1_2_a5/}
}
TY  - JOUR
AU  - T. A. Makarovskikh
TI  - The algorithms for constructing of cutter optimal path
JO  - Journal of computational and engineering mathematics
PY  - 2014
SP  - 52
EP  - 61
VL  - 1
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JCEM_2014_1_2_a5/
LA  - en
ID  - JCEM_2014_1_2_a5
ER  - 
%0 Journal Article
%A T. A. Makarovskikh
%T The algorithms for constructing of cutter optimal path
%J Journal of computational and engineering mathematics
%D 2014
%P 52-61
%V 1
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JCEM_2014_1_2_a5/
%G en
%F JCEM_2014_1_2_a5
T. A. Makarovskikh. The algorithms for constructing of cutter optimal path. Journal of computational and engineering mathematics, Tome 1 (2014) no. 2, pp. 52-61. http://geodesic.mathdoc.fr/item/JCEM_2014_1_2_a5/

[1] L. V. Kantorovich, V. A. Zalgaller, Rational Cutting of Industrial Materials, Nevskij Dialekt publ., St. Peterburg, 2012, 303 pp.

[2] M. A. Verkhoturov, P. Yu. Tarasenko, “Mathematical Support for a Path Optimization Problem of a Plane Figure Circuit Cutting”, Vestnik UGATU. Seriya «Upravlenie, Vychislitelnaya Tekhnika i Informatika», 10:2 (2008), 123–130

[3] A. A. Petunin, “About Some Strategies of the Programming of Tool Route by Developing of Control Programs for Thermal Cutting Machines”, Vestnik UGATU. Seriya «Upravlenie, Vychislitelnaya Tekhnika i Informatika», 13:2 (2009), 280–286

[4] T. Pisanski, T. W. Tucker, A. Zitnik, “Controllability of Sobolev-Type Integro-differential Systems in Banach Spaces”, Discrete Mathematics, 281:1–3 (2004), 237–246 | DOI | MR | Zbl

[5] H. Fleischner, Eulerian Graphs and Related Topics, Part 1, v. 2, Annals of Discrete Mathematics, 50, North Holland Publ., Amsterdam, 1991, ii–vii, VIII.1–C.3 pp. | MR | Zbl

[6] H. Fleischner, Eulerian Graphs and Related Topics, Part 1, v. 1, Annals of Discrete Mathematics, 45, North Holland Publ., Amsterdam, 1990, ii–ix, I.1–B.9 pp. | MR | Zbl

[7] H. Fleischner, L. W. Beineke, R. J. Wilson, Eulerian Graphs, Selected Topics in Graph Theory 2, Academic Press, London–New-York, 1983, 301 pp. | MR

[8] A. Kotzig, “Moves Without Forbidden Transitions in a Graph”, Mat.-Fiz. Casopis, 18:1 (1968), 76–80 | MR | Zbl

[9] A. V. Panyukov, T. A. Panyukova, “The Algorithm for Tracing of Flat Euler Cycles with Ordered Enclosing”, Proceedings of Chelyabinsk Scientific Center, 2000, no. 4 (9), 18–22 | MR

[10] T. Panyukova, “Cover with Ordered Enclosing for Flat Graphs”, Electronic Notes in Discrete Mathematics, 28 (2007), 17–24 | DOI | MR | Zbl

[11] T. Panyukova, “Ordered Enclosing Covers with Minimal Length of Additional Edges”, Abstracts of 8th French Combinatorial Conference (June 28 – July 2, 2010, Orsay, France), Orsay, France, 2010, 18 | MR

[12] T. A. Panyukova, A. V. Panyukov, “Algorithms for Construction of Ordered Enclosing Traces in Planar Eulerian Graphs”, The International Workshop on Computer Science and Information Technologies, Proceedings of Workshop (September 16 – 18, Ufa, USATU), v. 1, Ufa, USATU, 2003, 134–138

[13] T. Panyukova, “The special routes in plane graphs”, Sixth International Congress on Industrial Applied Mathematics (ICIAM07) and GAMM Annual Meeting (2007, Zurich), v. 7, Zurich, 2008, 2070015–2070016 | DOI

[14] T. Panyukova, “Covering with Ordered Enclosing for a Multiconneted Graph”, Abstracts of Seventh Czech-Slovak Symposium on Graph Theory, Combinatorics and Applications (July 7-13, 2013, Koshice, Slovakia), Koshice, 2013, 65

[15] T. A. Panyukova, “Optimal Eulerian coverings with ordered enclosing for plane graphs”, Diskretn. Anal. Issled. Oper., 18:2 (2011), 64–74 | MR | Zbl

[16] T. Panyukova, E. Savitskiy, “Allowed Eulerian Covers with Ordered Enclosing for Multiconnected Graph”, Statistika. Modelirovanie. Optimizatsiya, All-Russian conference (Chelyabinsk, South Ural State University), Pubbl. center of SUSU, 2011, 154–159 (in Russian)

[17] T. Panyukova, E. Savitskiy, “Optimization of Resources Usage for Technological Support of Cutting Processes”, Proceedings of the Workshop on Computer Science and Information Technologies, CSIT'2010 (September 13–19, Moscow – St.Petersburg, Russia), v. 1, Ufa, USATU, 2010, 66–70