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.