Generation of cycles of map cells for a simple planar graph

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.