Ranking and unranking planar embeddings
Kiem-Phong Vo, Wayne E. Dick, S. Gill Williamson · Linear and Multilinear Algebra · 1985
In this paper, we give a formula for computing the number of different planat embeddings of any planar biconnected graph. The enumeration method used in deriving the formula readily gives rise to efficient algorithms for the ranking, unranking and random generation of embeddings of the given graph. We also give linear time algorithms for checking planarity and constructing any particular embedding.