Generation of cycles of map cells for a simple planar graph

Authors

  • B.N. Ivanov Far Eastern Federal University (FEFU)

Keywords:

generation of cycles, enumeration of cycles, basis of cycles, graph map, nesting of cycles, fundamental cycles, chordless cycles

Abstract

A constructive method for generating the cycles of map cells of a simple planar graph is considered. These cycles are represented as a linear combination of DFS-basis cycles. The sought linear combinations are constructed explicitly on the basis of the allocated properties of the nesting structure of DFS-basis cycles and the map cells cycles of the graph. The map of a planar graph allows one to avoid the traditional approach used to generate such cycles and allows one to take into account the geometry of the map in the algorithm. The relation of neighborhood is defined on the set of the cycles, which induces the rooted tree of the nested cycle structure. The cells of the graph map are the result of traversal of the rooted tree. The complexity of the proposed algorithm is cubic relative to the number of the graph vertices. The application of this algorithm to solving the problems of planar subdivision is discussed.

Author Biography

B.N. Ivanov

References

  1. Иванов Б.Н. Решение задачи расчета оптимальных маршрутов судов в рамках геоинформационной системы «ОКЕАН» // Вычислительные методы и программирование. 2012. 13. 226-234.
  2. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. М.: Мир, 1989.
  3. Оре О. Теория графов. М.: Наука, 1980.
  4. Роджерс К.А. Укладки и покрытия. М.: Мир, 1968.
  5. Делоне Б.Н. О пустом шаре // Известия АН СССР. 1934. VII серия, № 6. 793-800.
  6. Sokhn N., Baltensperger R., Bersier L.F., Hennebert J., Ultes-Nitsche U. Identification of chordless cycles in ecological networks // Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering. Vol. 126. Berlin: Springer, 2013. 316-324.
  7. Pfaltz J.L. Chordless cycles in networks // IEEE 29th International Conference on Data Engineering Workshops (ICDEW). New York: IEEE Press, 2013. 223-228.
  8. Welch J. A mechanical analysis of the cyclic structure of undirected linear graphs // J. Assoc. Comput. Mech. 1966. 13. 205-210.
  9. Gibbs N.W. A cycle generation algorithm for finite undirected linear graphs // J. Assoc. Comput. Mech. 1969. 16. 564-568.
  10. Tarjan R. Enumeration of the elementary circuits of a directed graph // SIAM J. Comput. 1973. 2, N 3. 211-216.
  11. Jonson D.B. Finding all the elementary circuits of a directed graph // SIAM J. Comput. 1975. 4, N 1. 77-84.
  12. Mateti P., Deo N. On algorithms for enumerating all circuits of a graph // SIAM J. Comput. 1976. 5, N 1. 90-99.
  13. Tarjan R.E. Depth-first search linear graph algorithms // SIAM J. Comput. 1972. 1. 146-160.
  14. Syslo M.M. An efficient cycle vector space algorithm for listing all cycles of a planar graph // SIAM J. Comput. 1981. 10, N 4. 797-808.
  15. Wild M. Generating all cycles, chordless cycles, and Hamiltonian cycles with the principle of exclusion // Journal of Discrete Algorithms. 2008. 6. 93-102.
  16. Mahdi F., Safar M., Mahdi K. Detecting cycles in graphs using parallel capabilities of GPU // Digital Information and Communication Technology and Its Applications. Vol. 167. Berlin: Springer, 2011. 193-205.
  17. Kavitha T., Mehlhorn K., Michail D. New approximation algorithms for minimum cycle bases of graphs // Algorithmica. 2011. 59, N 4. 471-488.
  18. Рейнголд Э., Нивергельд Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980.
  19. Курош А.Г. Лекции по общей алгебре. М.: Наука, 1973.
  20. Алексеев В.Е., Таланов В.А. Графы. Модели вычислений. Структуры. Нижний Новгород: Изд-во ННГУ, 2005.
  21. Dogrusoz U., Krishnamoorthy M.S. Enumerating all cycles of a planar graph // Parallel Algorithms Appl. 1996. 10, N 1/2. 21-36.
  22. Deo N., Prabhu G.M., Krishnamoorthy M.S. Algorithms for generating fundamental cycles in a graph // ACM Trans. Math. Software. 1982. 8, N 1. 26-42.
  23. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. М.: Известия, 2011.
  24. Paton K. An algorithm for finding a fundamental set of cycles of a graph // Comm. ACM. 1969. 12, N 9. 514-518.
  25. Иванов Б.Н. Структуры вложенности поля изолиний в задаче градиентного заполнения // Вычислительные методы и программирование. 2006. 7, № 1. 155-165.

Published

16-05-2014

How to Cite

Иванов Б.Н. Generation of Cycles of Map Cells for a Simple Planar Graph // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2014. 15. 304-316

Issue

Section

Section 1. Numerical methods and applications