Institute of Computer Science III
University of Bonn
Databases * Information Systems * Software Engineering *
Pattern Recognition * Image Processing * Artificial Intelligence * Robotics
A simple linear time algorithm for embedding maximal planar graphs
Hermann Stamm-Wilbrandt
All existing algorithms for planarity testing/planar embedding can be grouped into two principal classes. Either, they run in linear time, but to the expense of complex algorithmic concepts or complex data-structures, or they are easy to understand and implement, but require more than linear time [2].
In this paper, a new linear-time algorithm for embedding maximal planar graphs is proposed. This algorithm is both easy to understand and easy to implement. The algorithm consists of three phases which use only simple, local graph-modifications.
In addition to planar embedding, the new algorithm allows to test graphs for maximal planarity. The generation of Straight Line Drawings by a technique of Read [12] can be naturally incorporated into the algorithm. We also demonstrate how to generate random (maximal) planar graphs.
The algorithm presented constitutes a first step towards a simple, linear-time solution for emedding general planar graphs.
Click here to obtain the full paper (PS, gzip, 72487 bytes, 14 pages)
webmaster@www.informatik.uni-bonn.de -
16.12.05