A Simple Planarity Criterion
Bernd Knauer · Journal of the ACM · 1975
An algorithm is presented which either directly establishes the nonplanarity of a graph G or completes G to a locally Hamiltonian graph 0 in such a way that G is planar if and only if G is.The plananty of (~ may be verffied readily by a theorem of Skupl~n.