On the linearity of testing planarity of graphs (Q1095918): Difference between revisions

In 1978, the author [Acta Math. Appl. Sinica 1, 395-406 (1978)] published a paper in which a characteristic theorem of planarity of a graph was provided as determining if another graph has a fundamental circuit with a certain property. However, the new graph is with, at worst, quadratic order of the vertex number of the original graph. This paper presents a new criterion of testing planarity of a graph based on what the author obtained before. Fortunately, it is equivalent to finding a spanning tree in another graph with only linear order of the vertex number of the original one in the worst case.