A linear algorithm for embedding planar graphs using PQ-trees (Q1083864)

This paper presents a simple linear algorithm for embedding (or drawing) a planar graph in the plane. The algorithm is based on the ''vertex- addition'' algorithm of \textit{A. Lempel}, \textit{S. Even}, and \textit{I. Cederbaum} [Theory of graphs, Int. Symp. Rome 1966, 215-232 (1967; Zbl 0197.502)] for the planarity testing, and is a modification of \textit{K. S. Booth} and \textit{G. S. Lueker}'s [J. Comput. Syst. Sci. 13, 335-379 (1976; Zbl 0367.68034)] implementation of the testing algorithm using a PQ-tree. Compared with the known embedding algorithm of \textit{J. E. Hopcroft} and \textit{R. E. Tarjan} [J. Assoc. Comput. Mach. 21, 549-568 (1974; Zbl 0307.68025)], this algorithm is conceptually simple and easy to understand or implement. Moreover this embedding algorithm can find all the embeddings of a planar graph.