A simple linear-time planar layout algorithm with a LEDA implementation

This note describes a simple linar-time algorithm for realising the embedding of a planar graph. The realisations are rather `bad' in the sense that the face areas can vary exponentially, but they provide a visual certificate of graph planarity, at least for graphs with not too many nodes. The algorithm takes as input a triangulated planar map, and computes coordinates for each node in a straight-line embedding. The paper includes a LEDA implementation of the algorithm.

This algorithm turns out to be very close (but not identical) to one published by Read in 1987. This paper has the merit, however, of including an implementation.