Planar embedding of hamiltonian graphs via efficient bipartation of circle graphs
Christoph Hundack, Hermann Stamm-Wilbrandt · 1994
We describe an easy way to check whether a hamiltonian graph of order n with a given hamiltonian cycle is planar. This is done by solving the bipartation problem for the corresponding circle graph. If the graph is planar an embedding is constructed. The algorithm runs in O(n) time and space.