Geodesic
The software for constructing a graph covering with ordered enclosing for multiconnected planar graphs
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 2 (2013) no. 2, pp. 111-117 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The problems of constructing such paths that correspond to definite restrictions have practical roots. For example, graph can present a cutting plan for cutting problem. A path covering all the edges of this graph determines the trajectory of cutting tool moving. The paper concerns the algorithm for constructing the optimal cover for any (may be multiconnected) graph by trails with ordered enclosing. This algorithm allows to find such a trajectory of cutting tool moving that a part cut off from a sheet does not require additional cuttings. It is shown that the considered algorithm has polynomial complexity.
Keywords: path, ordered enclosing, plane graph. 
@article{VYURV_2013_2_2_a9,
     author = {T. A. Panyukova and E. A. Savitskiy},
     title = {The software for constructing a graph covering with ordered enclosing for multiconnected planar graphs},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a Vy\v{c}islitelʹna\^a matematika i informatika},
     pages = {111--117},
     year = {2013},
     volume = {2},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURV_2013_2_2_a9/}
}
TY  - JOUR
AU  - T. A. Panyukova
AU  - E. A. Savitskiy
TI  - The software for constructing a graph covering with ordered enclosing for multiconnected planar graphs
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
PY  - 2013
SP  - 111
EP  - 117
VL  - 2
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VYURV_2013_2_2_a9/
LA  - ru
ID  - VYURV_2013_2_2_a9
ER  - 
%0 Journal Article
%A T. A. Panyukova
%A E. A. Savitskiy
%T The software for constructing a graph covering with ordered enclosing for multiconnected planar graphs
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
%D 2013
%P 111-117
%V 2
%N 2
%U http://geodesic.mathdoc.fr/item/VYURV_2013_2_2_a9/
%G ru
%F VYURV_2013_2_2_a9
T. A. Panyukova; E. A. Savitskiy. The software for constructing a graph covering with ordered enclosing for multiconnected planar graphs. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 2 (2013) no. 2, pp. 111-117. http://geodesic.mathdoc.fr/item/VYURV_2013_2_2_a9/

[1] D. Chebikin, “On k-edge-ordered graphs”, Discrete Mathematics, 2004, no. 281, 115–128

[2] H. Fleischner, Eulerian Graphs and Related Topics, Part 1, v. 1, no. 45, Ann. Discrete Mathematics, 1990, 450 pp.

[3] H. Fleischner, Eulerian Graphs and Related Topics, Part 1, v. 2, no. 50, Ann. Discrete Mathematics, 1991, 325 pp.

[4] T. Panyukova, “Eulerian Cover with Ordered Enclosing for Flat Graphs”, Electronic Notes in Discrete Mathematics, 28 (2007), 17–24

[5] T. A. Panyukova, “Optimal Eulerian Covers for Planar Graphs”, Discrete Analysis and Operation Research, 18:2 (2011), 64–74

[6] T. A. Panyukova, “Eulerian Cover with Ordered Enclosing for a Multiconnected Graph”, Materials of Third International Conference “Mathematical Modelling, Optimization and IT”, Evrica, Kishinev, 2012, 429–438

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

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

[9] T. Pisanski, T. W. Tucker, A. Zitnik, “Straight-ahead walks in Eulerian graphs”, Discrete Mathematics, 281 (2004), 237–246

[10] S. Szeider, “Finding paths in graphs avoiding forbidden transitions”, Discrete Applied Mathematics, 2003, no. 126, 261–273

[11] A. Zitnik, “Plane graphs with Eulerian Petrie walks”, Discrete Mathematics, 244 (2002), 539–549