Computer Recognition and Extraction of Planar Graphs from the Incidence Matrix

Abstract

A computational algorithm is presented for determining whether a graph is planar. All of the operations of the algorithm are expressed in terms of the incidence matrix of the graph. If the graph is nonplanar, the algorithm systematically identifies a set of edges whose deletion yields a subgraph that is planar. A simple procedure for drawing the planar subgraph is also presented. The algorithm has been programmed for a computer and is computationally efficient. The program can also be used to obtain a planar partition of a nonplanar graph. The algorithm is based on a decomposition theorem which reduces the problem of testing the planarity of an arbitrary graphGto the problem of testing the planarity of a set of "pseudo-Hamiltonian" graphs which are systematically formed fromG. The necessary and sufficient conditions that a pseudo-Hamiltonian graph be planar are presented. These conditions are expressed directly in terms of the incidence matrix of the graph. The incidence matrix implementation is applied to arbitrary graphs by means of the decomposition theorem. Several techniques which are necessary to insure the convergence and computational efficiency of the algorithm are given.