An Efficient Cycle Vector Space Algorithm for Listing All Cycles of a Planar Graph
Maciej M. Sysło · SIAM Journal on Computing · 1981
All known cycle vector space algorithms for listing cycles of a graph are inefficient, and in the worst case they compute all vectors of the cycle space. This is a very significant drawback of the cycle space approach. In this paper, a cycle vector space algorithm for enumerating all cycles of a planar graph, which produces only cycles of a graph and requires $O(n)$ space and $O(n + nc)$ time (where n and c denote the number of vertices and cycles of a graph, resp.), is presented. Thus we show that in the class of planar graphs, the cycle space approach can be as efficient as the backtrack algorithms.