Ranking and Unranking of the Planar Embeddings of a Planar Graph

Abstract

Let $\mathcal{G}$ be the set of all the planar embeddings of a (not necessarily connected) $n$-vertex graph $G$. We present a bijection $\Phi$ from $\mathcal{G}$ to the natural numbers in the interval $[0\dots |\mathcal{G}|-1]$. Given a planar embedding $\mathcal{E}$ of $G$, we show that $\Phi (\mathcal{E})$ can be decomposed into a sequence of $O(n)$ natural numbers each describing a specific feature of $\mathcal{E}$. The function $\Phi$, which is a ranking function for $\mathcal{G}$, can be computed in $O(n)$ time, while its inverse unranking function ${\Phi }^{-1}$ can be computed in $O(n\alpha (n))$ time. The results of this paper can be of practical use to uniformly at random generating the planar embeddings of a graph $G$ or to enumerating such embeddings with amortized constant delay. Also, they can be used to counting, enumerating or uniformly at random generating constrained planar embeddings of $G$.