Geodesic
Constructing of $OE$-postman path for a planar graph
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 7 (2014) no. 4, pp. 90-101 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The model of cutting plan can be presented as a planar graph for automated system of sheet material cutting process preparation. The aim of such modelling is a definition of the shortest path of a cutter having no parts requiring any additional cuttings. The paper is devoted to a problem of chines postman path constructing for a planar graph representing a cutting plan. This path has a restriction of ordered enclosing (i.e. cycle of passed edges does not contain inside not passed ones). The path satisfying this restriction is also called $OE$-path. This kind of restriction means the lack of additional cuttings of details. The recursive algorithm for constructing of this type of paths is considered in the paper. It is proved that this algorithm has a polynomial complexity. The developed software allows to solve the problem for an arbitrary planar graph. The software is tested for the typical cases of planar graphs.
Keywords: planar graph; Chinese postman problem; path; ordered enclosing; algorithm; software. 
@article{VYURU_2014_7_4_a6,
     author = {T. A. Panyukova},
     title = {Constructing of $OE$-postman path for a planar graph},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a, Matemati\v{c}eskoe modelirovanie i programmirovanie},
     pages = {90--101},
     year = {2014},
     volume = {7},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/VYURU_2014_7_4_a6/}
}
TY  - JOUR
AU  - T. A. Panyukova
TI  - Constructing of $OE$-postman path for a planar graph
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
PY  - 2014
SP  - 90
EP  - 101
VL  - 7
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/VYURU_2014_7_4_a6/
LA  - en
ID  - VYURU_2014_7_4_a6
ER  - 
%0 Journal Article
%A T. A. Panyukova
%T Constructing of $OE$-postman path for a planar graph
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
%D 2014
%P 90-101
%V 7
%N 4
%U http://geodesic.mathdoc.fr/item/VYURU_2014_7_4_a6/
%G en
%F VYURU_2014_7_4_a6
T. A. Panyukova. Constructing of $OE$-postman path for a planar graph. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 7 (2014) no. 4, pp. 90-101. http://geodesic.mathdoc.fr/item/VYURU_2014_7_4_a6/

[1] Kantorovich L. V., Zalgaller V. A., Rational Cutting of Industrial Materials, St. Peterburg, 2012, 304 pp.

[2] Fleischner H., Eulerian Graphs and Related Topics, Part 1, v. 1, Ann. Discrete Mathematics, 48, 1990, 420 pp.; G. Flyaishner, Eilerovy grafy i smezhnye voprosy, Mir, M., 2002, 335 pp.

[3] Fleischner H., Eulerian Graphs and Related Topics, Part 1, v. 2, Ann. Discrete Mathematics, 50, 1991, 356 pp. | MR | Zbl

[4] Szeider S., “Finding Paths in Graphs Avoiding Forbidden Transitions”, Discrete Applied Mathematics, 126 (2003), 261–273 | DOI | MR | Zbl

[5] Zitnik A., “Planar graphs with Eulerian Petrie Walks”, Discrete Mathematics, 244 (2002), 539–549 | DOI | MR | Zbl

[6] Pisanski T., Tucker T. W., Zitnik A., “Straight-Ahead Walks in Eulerian Graphs”, Discrete Mathematics, 281 (2004), 237–246 | DOI | MR | Zbl

[7] Chebikin D., “On k-Edge-Ordered Graphs”, Discrete Mathematics, 281 (2004), 115–128 | DOI | MR | Zbl

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

[9] Panyukova T., “Chain Sequences with Ordered Enclosing”, Journal of Computer and System Sciences International, 46:1 (2007), 83–92 | DOI | MR | Zbl

[10] Panyukov A. V., Panioukova T. A., “The Algorithm for Tracing of Flat Euler Cycles with Ordered Enclosing”, Proceedings of Chelyabinsk Scientific Center, 2000, no. 4(9), 18–22 (accessed November 20, 2000) http://elibrary.ru/download/18130929.pdf | MR

[11] Panyukova T. A., “Trails with Ordered Enclosing for planar graphs”, Discrete Analysis and Operation Research, 13:2, part 2 (2006), 31–43 (in Russian) | MR | Zbl

[12] Panyukova T. A., “Optimal Eulerian Covers for planar graphs”, Discrete Analysis and Operation Research, 18:2 (2011), 64–74 (in Russian) | MR | Zbl