This paper describes a linear time algorithm that is capable of testing and embedding planar graphs. The algorithm is based on the st-numbering of Even and Tarjan [1] and the “vertex-addition” algorithm of Lempel, Even, and Cederbaum [2]. The reader can study these concepts from Chapter 8 of [3]. Another important part of the algorithm is the use of PQ-trees [4] with suitable modifications by adding “direction indicators.”

The embedding of a planar graph is done conceptually by reordering the vertices in the adjacency lists according to their clockwise appearance around the adjacent vertex in a planar embedding. The main phases of the authors’ algorithm is as follows: First they test for planarity and obtain an st-numbering of the vertices. Then they consider the directed graph formed by orienting the edges from higher to lower numbered vertices; they perform the vertex addition step on this digraph using a PQ-tree and accordingly reorder the adjacency lists of the digraph. In the last phase, the edges (in the opposite direction) of the undirected graph are added to the adjacency lists in appropriate positions.

The paper also describes how the authors’ algorithm can be modified to obtain full possible embeddings of a planar graph which is based on the “expressions” given in [2].