A planarity algorithm based on the Kuratowski theorem
Peng-Siu Mei, Norman E. Gibbs · 1970
In the layout of integrated circuits and printed circuits, one often wants to know if a particular electrical network is planar, i.e., can be imbedded in the plane without having any line crossing another line. Our algorithm, when given a finite graph G can decide if G is planar. The algorithm was implemented in Fortran together with the Cycle Generation Algorithm for Finite Undirected Linear Graphs of Gibbs and used extensively to test the planarity of a large number of graphs. The distinguishing characteristic of this algorithm is its conceptual simplicity and its ease of implementation on a computer. The computer program took but a few days to write and debug.