Let $G$ be a plane $3$-connected graph; so it partitions the plane into regions bounded by faces. Let $\mathrm{deg}_v$ be the sequence of vertex degrees of $G$, and $\mathrm{deg}_f$ be the sequence of the number of edges bounding each face, or, equivalently, the vertex degrees in the dual of $G$. Not always do $\mathrm{deg}_v$ and $\mathrm{deg}_f$ uniquely determine $G$. Here is a $2$-connected triangulated example, but similar $3$-connected examples can be constructed. (Notation: $5^2 4^3 3^4 2^2 = 5,5,4,4,4,3,3,3,3,2,2)$.
Nonisomorphic $2$-connected graphs with the same $\mathrm{deg}_v$ and $\mathrm{deg}_f$ sequences.
Q1. I am seeking an algorithm that will take as input $\mathrm{deg}_v$ and $\mathrm{deg}_f$ sequences, and output a plane graph $G$ that realizes these sequences (if they are compatible sequences).
Algorithms exist for realizing $\mathrm{deg}_v$ (see, e.g., Mathworld Graphic Sequences), but here I have (a) planarity, and (b) the dual degree sequence.
Q2. I have a sense that $\mathrm{deg}_v$ and $\mathrm{deg}_f$ "usually" determine a unique plane $G$ (if they are mutually consistent). Is this intuition correct? Can you suggest a precise formulation of the question?
