Enumerating Hamiltonian Cycles in a Planar Graph Using Combinatorial Cycle Bases

Cycle bases belong to a k-connected simple graph\udused both for listing and enumerating Hamiltonian cycles\udcontained in a planar graph. Planar cycle bases have a weighted\udinduced graph whose weight values limited to 1. Hence making\udit was possible used in the Hamiltonian cycle enumeration\udprocedures efficiently. In this paper a Hamiltonian cycle\udenumeration scheme is obtained through two stages. First, i\udcycles out of m bases cycles are determined using an appropriate\udconstructed constraint. Secondly, to search all Hamiltonian\udcycles which are formed by the combination of i bases cycles\udobtained in the first stage efficiently. This efficiency achieved\udthrough a generation a class of objects as the representation of i\udcycle combinations among m bases cycles. The experiment\udconducted based on the proposed algorithm successfully\udgenerated and enumerated all the Hamiltonian cycles contained\udin a well-known example of planar graph