The number of distinct embeddings is exponential in the worst case triconnected planar graphs have a unique embedding. The Complexity of Planarity | Planar Undirected Graphs Graph Drawing 32 Planar Drawings and Embeddings a planar embedding is a class of topologically equivalent planar drawings a planar embedding prescribes the star of edges around each vertex the circuit bounding each face the number of distinct embeddings is exponential in the worst case triconnected planar graphs have a unique embedding Graph Drawing 33 The Complexity of Planarity Testing Planarity testing and constructing a planar embedding can be done in linear time depth-first-search Hopcroft Tarjan 74 de Fraysseix Rosenstiehl 82 st-numbering and PQ-trees Lempel Even Cederbaum 67 Even Tarjan 76 Booth Lueker 76 Chiba Nishizeki Ozawa 85 The above methods are complicated to understand and implement Open Problem devise a simple and efficient planarity testing algorithm. Graph Drawing .
