Mathematical model and algorithm for calculating the cycles of the cells of the graph map




graph map, map cells, graph cycles, cycle properties


The selected properties of the cycles of the DFS-basis block of a simple graph map allowed us to create a mathematical model for calculating the cycles of the cells of the graph map. According to this model, a practical algorithm for calculating the cycles of the graph map cells is proposed. The algorithm has a quadratic complexity relative to the number of vertices in the graph.

Author Biography

Boris N. Ivanov


  1. B. N. Ivanov, “Solution of the Optimal Ship Route Problem in the Framework of the OKEAN Geoinformation System,” Vychisl. Metody Programm. 13 (1), 226-234 (2012).
  2. J. T. Welch, “A Mechanical Analysis of the Cyclic Structure of Undirected Linear Graphs,” J. Assoc. Comput. Mach. 13 (2), 205-210 (1966).
  3. N. E. Gibbs, “A Cycle Generation Algorithm for Finite Undirected Linear Graphs,” J. Assoc. Comput. Mach. 16 (4), 564-568 (1969).
  4. R. Tarjan, “Enumeration of the Elementary Circuits of a Directed Graph,” SIAM J. Comput. 2 (3), 211-216 (1973).
  5. D. B. Jonson, “Finding all the Elementary Circuits of a Directed Graph,” SIAM J. Comput. 4 (1), 77-84 (1975).
  6. P. Mateti and N. Deo, “On Algorithms for Enumerating all Circuits of a Graph,” SIAM J. Comput. 5 (1), 90-99 (1976).
  7. R. Tarjan, “Depth-First Search Linear Graph Algorithms,” SIAM J. Comput. 1 (2), 146-160 (1972).
  8. F. Mahdi, M. Safar, and K. Mahdi, “Detecting Cycles in Graphs Using Parallel Capabilities of GPU,” in Digital Information and Communication Technology and Its Applications (Springer, Berlin, 2011), Vol. 167, pp. 193-205.
  9. T. Kavitha, K. Mehlhorn, and D. Michail, “New Approximation Algorithms for Minimum Cycle Bases of Graphs,” Algorithmica 59 (4), 471-488 (2011).
  10. J. L. Pfaltz, “Chordless Cycles in Networks,” in Proc. IEEE 29th Int. Conf. on Data Engineering Workshops, Brisbane, Australia, April 8-12, 2013 (IEEE Press, New York, 2013), pp. 223-228.
  11. B. N. Ivanov, “Generation of Cycles of Map Cells for a Simple Planar Graph,” Vychisl. Metody Programm. 15 (2), 304-316 (2014).
  12. O. Ore, Theory of Graphs (AMS Press, Providence, 1962; Nauka, Moscow, 1980).
  13. F. P. Preparatat and M. I. Shamos, Computational Geometry: An Introduction (Springer, Heidelberg, 1985; Mir, Moscow, 1989).
  14. B. E. Alekseev and V. A. Talanov, Graphs. Computational Models. Structures (Lobachevsky State Univ. of Nizhni Novgorod, Nizhni Novgorod, 2005) [in Russian].
  15. K. Paton, “An Algorithm for Finding a Fundamental Set of Cycles of a Graph,” Commun. ACM 12 (9), 514-518 (1969).
  16. E. M. Reingold, J. Nievergelt, and N. Deo, Combinatorial Algorithms. Theory and Practice (Prentice-Hall, Englewood Cliffs, 1977; Mir, Moscow, 1980).
  17. B. N. Ivanov, “Nesting Structures of the Isoline Field in the Gradient Filling Problem,” Vychisl. Metody Programm. 7 (2), 30-40 (2006).



How to Cite

Иванов Б. Н. Mathematical Model and Algorithm for Calculating the Cycles of the Cells of the Graph Map // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2021. 22. 294-305. doi 10.26089/NumMet.v22r419



Methods and algorithms of computational mathematics and their applications