Institute of Computer Science III
University of Bonn
Databases * Information Systems * Software Engineering * Pattern Recognition * Image Processing * Artificial Intelligence * Robotics

Planar embedding of hamiltonian graphs via efficient bipartation of circle graphs

Christoph Hundack and Hermann Stamm-Wilbrandt

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.

Click here to obtain the full paper (PS, gzip, 68084 bytes, 15 pages)

webmaster@www.informatik.uni-bonn.de - 16.12.05