A direct method for calculating cell cycles of~a~block~map of a simple planar graph

B. N. Ivanov

Prikladnaâ diskretnaâ matematika, no. 4 (2022), pp. 69-83.

Résumé

The proposed algorithm for calculating the cycles of the cells the simple planar graph block map is an extension of the classical depth-first search algorithm for cycles of the DFS-basis. The key idea of the modification of this algorithm is the strategy of right-hand traversal when passing the graph in depth. The vertex with the minimum coordinate on the OY axis is assigned as the starting vertex in the right-hand traversal. The exit from the initial vertex is performed along the edge with the minimum polar angle. The continuation of the traversal from each next vertex is carried out along an edge with a minimum polar angle relative to the edge along which arrived at the current vertex. A two-level structure of nested cycles is introduced. This is the main level and the zero level of nesting. All cycles of the basis belong to the main level. Each of the cycles can additionally have a zero level of nesting in another main cycle for it, if it is nested in the main cycle and not nested in any other cycle from the main cycle. With the right-hand traversal, zero nesting cycles are adjacent to the main cycle and do not have common vertices outside the main cycle. These two properties allowed in each basis cycle sequentially select and exclude from it all its zero nesting cycles, using the symmetric difference operation. It is shown that the rest of the basic cycle is the cycle of the block map cell. The complexity of each step of the proposed algorithm does not exceed the quadratic complexity with respect to the number of vertices of the simple planar graph.

Détail

Keywords: planar graph cycles, graph block cycles, planar graph.

Bibliographie

[1] Ore O., Theory of Graphs, AMS Press, Providence, 1962, 336 pp. | MR

[2] Preparatat F. P. and Shamos M. I., Computational Geometry: An Introduction, Springer Verlag, N.Y., 1989, 478 pp. | MR

[3] Welch J., “A mechanical analysis of the cyclic structure of undirected linear graphs”, J. Assoc. Comput. Mech., 13 (1966), 205–210 | DOI | MR

[4] Gibbs N. W., “A cycle generation algorithm for finite undirected linear graphs”, J. Assoc. Comput. Mech., 16 (1969), 564–568 | DOI | MR

[5] Tarjan R., “Enumeration of the elementary circuits of a directed graph”, SIAM J. Comput., 2 (1973), 211–216 | DOI | MR

[6] Jonson D. B., “Finding all the elementary circuits of a directed graph”, SIAM J. Comput., 4 (1975), 77–84 | DOI | MR

[7] Mateti P. and Deo N., “On algorithms for enumerating all circuits of a graph”, SIAM J. Comput., 5:1 (1976), 90–99 | DOI | MR

[8] Tarjan R., “Depth-first search linear graph algorithms”, SIAM J. Comput., 1 (1972), 146–160 | DOI | MR

[9] Mahdi F., Safar M., and Mahdi K., “Detecting cycles in graphs using parallel capabilities of GPU”, Digital Inform. Commun. Techn. Appl. (DISTAP), 167 (2011), 193–205

[10] Kavitha T., Mehlhorn K., and Michail D., “New approximation algorithms for minimum cycle bases of graphs”, J. Algorithmica, 59:4 (2011), 471–488 | DOI | MR

[11] Pfaltz J. L., “Chordless cycles in networks”, IEEE 29th Intern. Conf. ICDEW, 2013, 223–228

[12] Ivanov B. N., “Generation of cycles of map cells for a simple planar graph”, Vychislitel'nye Metody i Programmirovanie, 2014, no. 15, 304–316 (in Russian)

[13] Alekseev B. E. and Talanov V. A., Graphs. Computational Models. Structures, Lobachevsky State University, N. Novgorod, 2005, 307 pp. (in Russian)

[14] Paton K., “An algorithm for finding a fundamental set of cycles of a graph”, Comm. ACM, 12:9 (1969), 514–518 | DOI

[15] Reingold E. M., Nievergelt J., and Deo N., Combinatorial Algorithms. Theory and Practice, Prentice-Hall, Englewood Cliff, 1977, 476 pp. | MR | MR