A new approach to the linearity of testing planarity of graphs

In testing planarity of graphs, there are many criteria. The earliest one as known is the Kuratowski's theorem, then Whitney's, Maclane's, and so forth. Since the early sixties, people have begun researches on algorithms. Up to 1974, Hopcroft and Tarjan found an algorithm with a computing time being a linear function of the order of a graph. This is the linearity concerned here.This paper presents a new approach to the linearity by means of transforming the problem of testing planarity of a graphG into that of finding a spanning tree on another graphH, called an auxiliary graph ofG, with the order ofH being a linear function of that ofG. And moreover, we can also make the size ofH be a linear function of that ofG. The whole procedure is based on the building up of a theory of linear equations onGF (2) related toG.This was a report invited by RUTCOR, The State University of New Jersey, Rutgers, U. S. A. in 1984. And, the main part of this paper was completed during the author's stay at the Department of C & O, University of Waterloo, Canada.