A linear algorithm for embedding planar graphs using PQ-trees

摘要

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 Lempel, Even, and Cederbaum (“Theory of Graphs,” Intl. Sympos. Rome, July 1966, pp. 215–232, Gordon & Breach, New York, 1967) for the planarity testing, and is a modification of Booth and Lueker's (J. Comput. System Sci. 13 (1976), 335–379) implementation of the testing algorithm using a PQ-tree. Compared with the known embedding algorithm of Hopcroft and Tarjan (J. Assoc. Comput. Mach. 21, No. 4 (1974), 549–568), this algorithm is conceptually simple and easy to understand or implement. Moreover this embedding algorithm can find all the embeddings of a planar graph.