On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm

We give a detailed description of the embedding phase of the Hopcroft and Tarjan planarity testing algorithm The embedding phase runs in linear time An implemen tation based on this paper can be found in MMN An undirected graph G VE is called planar if it can be mapped into the plane without edge crossings ie the vertices of G are mapped into distinct points in the plane and the edges of G are mapped into disjoint Jordan curves connecting their endpoints Such a mapping is called a planar geometric embedding Two geometric planar embeddings are called equivalent if there is an homeomorphism of the plane transforming one into the other An equivalence class of geometric planar embeddings is called a planar topological embedding or simply planar embedding A planar embedding of a planar graph induces a cyclic ordering on the edges incident to any xed vertex namely the clockwise ordering of the edges around their common endpoint A graph G together with a cyclic ordering on the edges incident to each vertex is called a combinatorial embedding it is called a planar combinatorial embedding if it is induced by some planar embedding Dierent planar embeddings can give rise to the same combinato rial embedding However a planar combinatorial embedding of a connected graph uniquely determines its topological embedding on the sphere In the plane it determines the topo logical embedding up to selection of the outer face Recall that an embedding into the plane can be obtained from an embedding on the sphere by polar projection The pole can be put into any face There are linear time algorithms dFPP Sch to convert a planar combinatorial embedding into a geometric embedding eg the algorithm by Schnyder puts the vertices of an n node graph onto an n n grid and realizes the edges by straight line segments Hopcroft and Tarjan HT gave an algorithm that tests the planarity of an undirected graph in linear time Alternative linear time algorithms were developed by Lempel Eve