On the determination of planar graphs.

Abstract

Various algorithms for testing the planarity of a graph are reviewed. The Phung-Chan algorithm is improved by modifying the method of application of the necessary and sufficient condition that a pseudo-Hamiltonian graph be planar and the method of determination of circuit C(k) with as many edges as possible, and from which the pseudo- Hamiltonian graph is defined. By application of the proposed algorithm it is proved that the algorithm can be applied to an arbitrary graph. Using this proposed algorithm, the rate of convergence of the algorithm is increased and the computer storage requirement is minimized.