COUNTING EMBEDDINGS OF PLANAR GRAPHS USING DFS TREES

Previously counting embeddings of planar graphs used P-Q trees and was restricted to biconnected graphs. Although the P-Q tree approach is conceptually simple, its implementation is complicated. In this paper, the author solves this problem using DFS trees, which are easy to implement. The author also gives formulas that count the number of embeddings of general planar graphs (not necessarily connected or biconnected) in O(n) arithmetic steps, where n is the number of vertices of the input graph. Finally, the algorithm can be extended to generate all embeddings of a planar graph in linear time with respect to the output.