(Esta página em português.)
(Click here for the sources of SH algorithm and the sources of the master's dissertation.)
Sometimes is useful to determine if a given graph can be drawn in the plane with no crossing edges. Such a drawing is plane. Given a graph, if there is a plane drawing for the graph then the graph is planar (see figure 1). For instance, in VLSI circuits, is useful to obtain a plane drawing of a graph representing an electric circuit.

A simple characterization for planar graphs was given by Kuratowski [8]. He showed that every nonplanar graph has a subdivision of or a subdivision of (see figure 2). Conversely, no planar graph has a subdivision of such graphs. A subdivision of or in a graph is a Kuratowski's subgraph.
Although elegant, the Kuratowski's characterization doesn't give a practical algorithm for planarity testing. Besides, it is not clear how to calculate a plane drawing through this characterization.
A possible strategy to decide if a graph is planar is increasingly build a plane drawing for . If a plane drawing of is completed, then is planar. Otherwise, ideally, a Kuratowski's subgraph is found in , justifying the nonplanarity of . The first algorithm using this strategy for planarity testing was proposed by Auslander and Parter [1]. Given a graph , the algorithm begins finding a circuit in . The resulting graph removing this circuit from consists of connected 'parts'. The algorithm is called recursively to obtain a plane drawing for each of these parts plus the circuit. Then, these drawings are combined, if possible, to obtain a plane drawing for . If it is not possible, then a Kuratowski's subgraph is found in . The Auslander and Parter's algorithm had an error which was corrected by Goldstein [6], resulting the Auslander, Parter and Goldstein's algorithm (APG). The complexity time of this algorithm is cubic.
Lempel, Even and Cederbaum [9] (LEC) presented an alternative way to increasingly build a plane drawing of a given graph. This algorithm starts with a drawing of a single vertex and adds to the drawing all the edges incident to that vertice. Then, it adds a new vertice incident to an added edge and all the edges incident to this new vertice. The process continues as the following. Each iteration begins with a plane drawing of part of the graph and consists of adding a new vertice and all edges incident to this vertice to the current plane drawing. The process continues until the graph has been completely drawn in the plane or the graph has been detected as nonplanar. This kind of algorithm is a vertex addition algorithm. Tarjan [13] presented an implementation for LEC wich runs in quadractic time.
In 1974, Hopcroft and Tarjan [7] presented the first lineartime algorithm to decide if a graph is planar. This algorithm is an implementation for APG's algorithm.
Hopcroft and Tarjan (HT) didn't give much details of how their planarity testing algorithm can be extended to calculate a plane drawing of the given graph. A complete description of this phase of this algorithm was done by Mehlhorn and Mutzel [10] and the respective implementation by Mutzel [11]. So far, there isn't a known lineartime implementation for HT's algorithm that calculates Kuratowski's subgraphs for nonplanar graphs.
In 1976, Booth and Lueker [2] presented a lineartime implementation for LEC's algorithm, using a data structure named PQtree. Recently, Shih and Hsu [12] and Boyer and Myrvold [3] described similar implementations for LEC's algorithm. Both run in lineartime and avoid using PQtrees.
The two most discussed algorithms are APG's and LEC's. Canfield and Williamson [4] compare these two algorithms and argument that, at the same time these algorithms are seen as different methods, they have many similarities.
Figure 3 shows a summary of the running time of the main planarity algorithms available nowadays.